백준 3078 좋은 친구

dasd412·2022년 7월 11일
0

코딩 테스트

목록 보기
54/71

문제 설명

상근이는 환갑을 바라보던 나이에 수능 시험을 다시보고 교대에 입학했고, 초등학교 선생님으로 취직했다.

상근: 요즘 애들은 친구를 사귀지 않나봐. 내가 앞에서 보고 있으면, 친구가 있는 학생이 별로 없는 것 같아.
??: 오빠! 오빠는 말콤의 친구와 성적이라는 책 안 읽어 봤어? 이 책에는 성적과 친구가 무슨 관계가 있는지 나와. 요즘 애들은 친구를 사귀기 전에 먼저 그 친구의 반 등수를 살펴봐. 말콤은 이 연구를 하기 위해서 6년동안 초등학교에서 선생님으로 위장 했었지. 하지만, 6년이라는 시간을 초등학교에서 보냈지만, 그 사람은 결국 결론을 얻지 못했어.
상근: 근데?
??: 말콤이 어느 날 자신이 초등학생이 되어 학교를 활보하는 꿈을 꾸었어. 근데 잠을 깨고 나니 내가 꿈을 꾸고 초등학생이 된건지, 아니면 초등학생이 꿈을 꾸고 지금의 내가 되어있는지를 모르겠는거야. 그래서 말콤은 상식적인 사고 방식에 큰 의문을 가졌지. 그 때 말콤은 깨달았던거야. 초등학교 친구는 부질없구나. 그제서야 알게된거야. 모든 학생은 자신과 반 등수의 차이가 K를 넘으면 친구가 아니라는거.
상근: 아? 근데 K는 어떻게 구해?
??: K는 문제에서 주어지지. 근데, 더 중요한 사실이 있어. 친구와 좋은 친구의 차이야. 말콤이 친구와 성적을 쓰고 2년 뒤에 낸 책인 좋은 친구라는 책에는 좋은 친구는 이름의 길이가 같아야 된다는 말이 나와.
상근: 아! 그럼 난 오늘 집에 가서 우리 반에 좋은 친구가 몇 쌍이나 있는지 구해봐야 겠어!

상근이네 반의 N명 학생들의 이름이 성적순으로 주어졌을 때, 좋은 친구가 몇 쌍이나 있는지 구하는 프로그램을 작성하시오. 좋은 친구는 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구이다.

입력 조건

첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다.

출력 조건

첫째 줄에 좋은 친구가 몇 쌍이 있는지 출력한다.


전체 코드

import sys
from collections import deque

n, k = list(map(int, sys.stdin.readline().split()))
names = []
for _ in range(n):
    names.append(sys.stdin.readline().rstrip())

# 문자열의 최대 길이는 21이다.
length_array = [0] * 21

answer = 0

# 큐를 활용하면, 슬라이딩 윈도우와 비슷한 효과를 낼 수 있다.
# 큐에서 빠져나가는 것을 left ++, 큐에 들어오는 것을 right ++ 라고 볼 수 있기 때문이다.
queue = deque()

for name in names:
    # 각 이름의 길이를 큐에 넣는다. 즉, 윈도우를 오른쪽으로 이동한다. right ++
    length = len(name)
    queue.append(length)
    # 다음 코드의 length_array는 현재 큐 상태(또는 현재 슬라이딩 윈도우 상태)에서 length(이름의 길이)가 몇 개 있는 지를 뜻한다.
    length_array[length] += 1

    # 윈도우를 오른쪽으로 이동했는데, 현재 큐의 길이가 k+1를 넘으면 등수 차이가 k를 넘으므로
    if len(queue) > k + 1:
        # 윈도우 왼쪽 부분 역시 오른쪽으로 이동시킨다. left ++
        pop = queue.popleft()
        # 현재 윈도우 내에서 제외된 이름의 길이 개수를 하나 줄인다.
        length_array[pop] -= 1

    # 자기 자신과는 쌍을 맺어선 안되므로 -1 해준다.
    answer += (length_array[length] - 1)

print(answer)

배운 것

  1. 슬라이딩 윈도우는 큐를 이용해서 표현할 수 있다.
  2. 딕셔너리(또는 배열)와 1.의 큐를 이용하면, 현재 슬라이딩 윈도우 내 의 개수를 빠르게 알아낼 수 있다.

참고

https://velog.io/@sein/Python-%EB%B0%B1%EC%A4%80-3078%EB%B2%88-%EC%A2%8B%EC%9D%80-%EC%B9%9C%EA%B5%AC

profile
아키텍쳐 설계와 테스트 코드에 관심이 많음.

0개의 댓글