백준-3078 좋은 친구

문제

이 문제는 입력하는 데이터 값이 300,000까지로 되게 큰편이다. 그래서 완전 탐색이라던가 이런건 당연히 시간초과가 난다.

이 문제는 queue를 사용해 sliding window개념을 통해 풀어야 한다.
되게 까다로운 문제였다..

생각

1. 친구의 이름의 길이의 수가 정해져 있다. (2 ~ 20) 그러므로 이를 이용해야 겠다는 생각을 했다.
2. nameLen이라는 인덱스가 친구의 이름 길이인 리스트 각 원소에 큐를 집어 넣었다. 각 원소마다 큐를 넣어서 입력되는 등수에 따라 popleft와 append를 통해서 계산하기 위함이다.
3. 이름은 무의미하므로 이름의 길이만 입력받는다.
4. 입력된 길이에 대해서 nameLen[len(input())]인 큐에 등수를 넣을건데 아무것도 없다면 그냥 넣고, 무언가 있다면 친구 쌍을 구하기 위해서 len(nameLen[len(input())])을 더해준다. 이 것은 큐의 길이를 더해주는 것이다. 그리고 새로 등수를 큐에 추가해주고, 만약 K보다 큰 차이가 난다면 popleft해주면 된다.

코드

from collections import deque

N, K = map(int, input().split())

nameLen = []
for _ in range(21):
    nameLen.append(deque([]))
# 이름의 길이를 가지고있는 배열
# 각 원소는 큐로이루어져있고 이큐에 등수가 들어갈 것이다.

cnt = 0
for ranking in range(N):
    personNameLength = len(input())
    while True:
        if len(nameLen[personNameLength]) == 0:
            nameLen[personNameLength].append(ranking)
            break;
        if ranking - nameLen[personNameLength][0] <= K:
            cnt += len(nameLen[personNameLength])
            nameLen[personNameLength].append(ranking)
            break;
        if ranking - nameLen[personNameLength][0] > K:
            nameLen[personNameLength].popleft()
            continue;
print(cnt)

느낀점

• BFS에서 큐를 좀 써봤었는데 그이후론 처음 써봤다. 그래서 그런지 좀 헤맸지만 좀더 큐를 잘이해하게된 계기가 된거 같다.