https://www.acmicpc.net/problem/3078
3078번: 좋은 친구
첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다.
www.acmicpc.net
슬라이딩 윈도우를 활용한다고 하여도.. 같은 길이의 문자열을 찾으려면 K개의 범위를 다 돌아봐야 하니까 시간초과가 날 것 같은데... 하는 생각에 오래 고민하다가 슬라이딩 윈도우의 장점을 사용하기 위한 방법을 생각해보았다.
바로 문자열의 길이를 인덱스로 하는 배열을 따로 만든 후에 같은 길이의 문자가 윈도우 안에 있는경우 그걸 인덱스로 한 값을 +1 해주는 방식이었다. 이렇게 하면 큐에서 하나가 dequeue 되면 해당 인덱스의 값도 -1 해주면 되고, 새로 들어오는 문자열의 길이는 해당 인덱스에 +1 해주면 되니까 비교를 위해 윈도우를 굳이 한 번씩 다 돌아볼 필요가 없다.
대신 만약 같은 길이의 문자가 a개 있는 경우에는 aC2 (조합) 을 이용해야 하는데 이걸 어떻게 구현할까.. 고민하다가 하나씩 문자의 개수가 추가될 때 문자가 1개 이상인 경우 즉 쌍을 맞출 수 있는 경우에 새롭게 추가된 문자와 기존에 있는 모든 문자가 새로운 쌍을 이루게 되므로 기존에 존재하는 문자의 개수를 더해주었다.
말로 설명하자니 어려운데 코드로 보면 이해가 될 것이다.
1. 문자열의 길이를 배열로 받는다. 순위는 인덱스가 되므로 따로 받을 필요가 없다.
2. 큐를 하나 만들고, 같은 길이의 문자 개수를 저장할 배열 num을 만들어 0으로 초기화한다.
3. 처음 만들어지는 범위가 0~K인 윈도우를 큐에 추가하고, 문자열의 길이를 인덱스로 하여 하나씩 더해준다. 이때, 더한 후 문자의 개수가 >1 이면 문자의 개수 - 1 만큼 정답에 더해준다.
4. 이후로는 슬라이딩 윈도우를 이용하여 하나씩 dequeue하고 enqueue해주며 위의 과정을 반복한다.
import sys
from collections import deque
N, K = map(int, sys.stdin.readline().split())
arr = []
for _ in range(N):
name = sys.stdin.readline().rstrip()
arr.append(len(name))
q = deque()
num = [0] * 21
ans = 0
for i in range(K+1):
q.append(arr[i])
num[arr[i]] += 1
if (num[arr[i]]>1):
ans += num[arr[i]]-1
for i in range(K+1, N):
num[q.popleft()] -= 1
q.append(arr[i])
num[arr[i]] += 1
if (num[arr[i]]>1):
ans += num[arr[i]]-1
print(ans)
'알고리즘💻 > 스택&큐&덱' 카테고리의 다른 글
BOJ 20923번: 숫자 할리갈리 게임 (0) | 2021.07.23 |
---|---|
BOJ 18115번: 카드 놓기 (0) | 2021.07.22 |
BOJ 2304번: 창고 다각형 (0) | 2021.07.22 |
BOJ 2347번: 풍선 터뜨리기 (0) | 2021.07.12 |
BOJ 4889번: 안정적인 문자열 (0) | 2021.04.06 |