[백준] 3078번 - 좋은친구 (파이썬)

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

3078번: 좋은 친구

 

[코드]

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())

queue = []
[queue.append(deque()) for _ in range(19)]

answer = 0
for i in range(N):
    name_len = len(sys.stdin.readline().strip()) - 2
    while queue[name_len]:
        if i - queue[name_len][0] <= K:
            answer += len(queue[name_len])
            break
        else:
            queue[name_len].popleft()
    queue[name_len].append(i)
print(answer)

 

[문제설명]

처음 문제풀때 문제자체를 잘못 이해했다.

좋은 친구를 구할 때 말콤 기준으로 K등수 범위내에서 말콤과 같은 글자 수를 말콤의 좋은친구라고 판단하였는데 그게 아니였다.

각각 K등수 차이나는 범위내에서 이름의 글자수가 같은 좋은 친구의 쌍을 구하는 것이었다.

 

두번째로 이해가 가지 않는 부분은 좋은친구 "쌍" 을 구하는 것이었다.

예를들면 다음과 같다. 

K = 2 이고

1등 김일

2등 김이박

3등 김삼

4등 홍길동

5등 김오

일때

김일과 김삼의 등수차는 2이므로 (김일, 김삼) 한쌍

김삼과 김오의 등수차는 2이므로 (김삼, 김오) 한쌍

위의 예에서는 두쌍을 찾을 수 있다.

 

[핵심 아이디어]

전체 풀이는 구글링을 통해 쉽게 찾을 수 있으므로 핵심 아이디어만 설명하면 다음과 같다.

이름 길이별로 각각 큐를 생성해서 써야한다. 하지만 큐를 써서 어떻게 쌍의 개수를 구하는 지는 햇갈릴 것이다.

이름의 길이가 3인 경우를 예를 들어보자. 그러면 queue[3-2] 의 큐 하나만 신경쓰면 된다.

queue[1]에 삽입되는 모든 이름길이는 3이며(따라서 등수만 입력),  등수가 높은 순서대로 입력이 되므로 큐 front 에 있는 값은 새로 삽입해야하는 값보다 반드시 작다. 

이때 새로운 이름을 큐에 넣을 때 새로운 이름 기준으로 K등수내의 쌍을 구하고 싶다.(큐에는 등수만 들어간다)

따라서 큐의 front 가 K범위내인지 체크해본다.

K 범위 이내이면 front 부터 back까지 K 범위 이내이므로 새로운 이름 기준 쌍 개수는 큐의 사이즈 이다.

K 범위 밖이면 pop 하면서 K 범위 이내일때까지 반복한다.

그리고 큐에 새로운 등수를 삽입한다.

이름의 길이가 2 ~ 20까지 인 경우 전부다 합하면 정답을 구할 수 있다.

 

[주의사항]

sys.stdin.readline()로 입력받으면 문자열 끝에 \n도 입력받음

strip() 함수를 통해 공백문자 제거해야함 (참고 https://yeonkevin.tistory.com/85)

[참고]

큐에서 [0] 이 front, [-1] 이 back