[BOJ] 3078번 좋은 친구 (C++)
문제 (https://www.acmicpc.net/problem/3078)
3078번: 좋은 친구
첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다.
www.acmicpc.net
슬라이딩 윈도우로 해결한 문제!!!
문제 설명이 엄청 길지만,, 요약하자면 좋은 친구의 정의는 아래와 같고 좋은 친구가 몇 쌍 있는지 출력하면 된다.
좋은친구: 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구
pair (등수, 이름의 길이) 형태로 입력을 받았다.
i번째(i등) 학생은 크기가 k인 창문 내의 다른 학생들 중, 이름의 길이가 같은 학생과 좋은 친구 사이인 것이다.
while문에서 사용한 map은 (key: 이름의 길이 n = value: 창문 내에 이름의 길이가 n인 학생의 수) 형태이다.
- end 값을 증가시키며 새로운 값(학생)을 처리한다. 즉 창문을 확장시키며 새로운 값이 들어온 것이다. (line 49)
- 창문에 값을 넣다가 창문의 크기가 k가 되면? 크기가 k인 현재 창문 내에 좋은 친구가 몇 쌍 있는지 계산한다.
=> 이때 창문 내에 존재하는 모든 쌍이 아닌 start가 가리키는 학생 기준으로 좋은 친구 쌍을 구한다!!! (line 53)
- 창문이 이동하면서 범위를 벗어난 값(start가 가리키는 값)을 제거하고 start를 증가시킨다. (line 43)
- end의 값이 n과 같아지면 start만 증가시키며 쌍의 개수를 구한다. (line 31)
[소스코드]
