백준(BOJ) 3078 좋은 친구(Python)

문제 내용.

 

큐로 푼 문제.

이름의 길이에 각각 큐를 만들어놓고 거기에 등수를 집어넣는다.

이때 집어넣기 전 큐가 비어있지 않으면 현재 큐에 있는 등수 중 k 이상 차이나는 등수를 모두 pop해준다.

그러고 나면 큐에 있는 등수들은 모두 현재 집어넣는 등수와 '좋은 친구'인 경우 밖에 없다.

큐의 크기를 ans에 더하고 등수를 해당 큐에 집어넣는 과정을 반복하면 된다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)
n,k=map(int,input().split())
MAP=[deque() for i in range(21)]
ans=0
for i in range(n):
    x=input().rstrip()
    while MAP[len(x)] and i-MAP[len(x)][0]>k:
        MAP[len(x)].popleft()
    ans+=len(MAP[len(x)])
    MAP[len(x)].append(i)
print(ans)

재활 쉽지 않다.