이 문제는 입력하는 데이터 값이 300,000까지로 되게 큰편이다. 그래서 완전 탐색이라던가 이런건 당연히 시간초과가 난다.
이 문제는 queue를 사용해 sliding window개념을 통해 풀어야 한다.
되게 까다로운 문제였다..
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)