[백준][Python] 3078번 좋은 단어 - 큐

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

3078번: 좋은 친구

 

 

Hint

이름 길이 별로 큐를 생성

 

Python

import sys
n, k = map(int, sys.stdin.readline().split())
#arr = [ sys.stdin.readline().rstrip() for _ in range(n) ] #성적 순

# 규칙 : 반 등수의 차이가 자신과 K가 넘으면 친구가 아니다
# 좋은 친구 : 친구 중에서 이름의 길이가 같은 친구

# 이름 길이 별로 큐를 생성
arr = [[] for _ in range(21)]

cnt = 0 
for i in range(n):
    name = sys.stdin.readline().rstrip()
    
    while arr[len(name)] and abs(arr[len(name)][0]-i)>k:
        del arr[len(name)][0]
        
    cnt += len(arr[len(name)])
    arr[len(name)].append(i)
    
print(cnt)

 

 

 

시간 초과

k의 길이가 커질 수록 오래 걸린다는 단점

import sys
n, k = map(int, sys.stdin.readline().split())
arr = [ sys.stdin.readline().rstrip() for _ in range(n) ] #성적 순

# 규칙 : 반 등수의 차이가 자신과 K가 넘으면 친구가 아니다
# 좋은 친구 : 친구 중에서 이름의 길이가 같은 친구

cnt = 0 
for i in range(len(arr)-1):
    for j in range(i+1, min(len(arr),i+k+1)):
        if len(arr[i]) == len(arr[j]):
            cnt+=1
print(cnt)