BOJ 3078번: 좋은 친구

https://www.acmicpc.net/problem/3078

3078번: 좋은 친구

슬라이딩 윈도우를 활용한다고 하여도.. 같은 길이의 문자열을 찾으려면 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)