백준 3078번 좋은 친구

얘는 2021년 05월 08일.....

---

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

문제 요약

n명의 학생으로 이루어진 반의 학생 명단이 성적 순으로 주어진다

이들 중 등수가 k 이내로 차이나는 학생들이 이름의 글자 수가 같으면 절친이다

절친이 몇 쌍이나 있는지 구해보아라

티어 골드3인 문제여서 굉장히 쫄았었는데 생각보다 쉽게 해결했다

6 3
CYNTHIA
LLOYD
STEVIE
KEVIN
MALCOLM
DABNEY

내 풀이

학생들을 앞에서부터 차례로 큐에 넣는다

위 예제를 예로 들면 등수 차이가 3이므로 큐에는 4명까지 넣는다

큐에 넣으면서 이름의 길이를 체크한다

[0 for i in range(21)]

이름이 2글자부터 20글자 까지이므로 큐 안에 있는 사람이 글자수별로 각각 몇명이 있는지 저장한다

위 예제에서 처음 4명을 보면 5글자 2명, 6글자 1명, 7글자 1명이므로

[0,0,0,0,0,2,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0]

이렇게 되어야 한다

큐에 4명이 다 찼으니 앞에서 한명씩 빼면서 빠져나가는 사람과 같은 길이가 몇명이 있는지 바로 위 리스트를 통해 확인할 수 있다

처음 빠져나가는 학생은 7글자이고 리스트에는 1명(자신 포함) 이므로 0쌍이다

빠져나가면 당연히 위 리스트에서도 제거해줘야한다

한명이 빠져나가 3명이 되었으니 뒤에는 새로 한명이 들어온다

두번째 LLOYD 가 빠져나갈 때 5글자인 사람의 수는 2명(본인 포함)이므로 1쌍을 추가해준다

만약 3이 써있었다고 가정하면 본인 포함 3명인 것이므로 2쌍을 추가해야 할 것이다

위 과정을 큐를 다 비울 때 까지 반복해주면 된다

코드화하면

from sys import stdin
from collections import deque

n, k = list(map(int, stdin.readline().split()))
namelist = [stdin.readline().rstrip() for i in range(n)]
namelen = [0 for i in range(21)]
q = deque()
ans = 0

for i in namelist:                 #namelist를 다 소모할 때 까지 반복
  if len(q)!=k+1:                  #이걸 하고 나면 큐에 이름이 남아있다
    q.append(i)
    namelen[len(i)]+=1
  if len(q)==k+1:
    ans = ans + namelen[len(q[0])] - 1
    namelen[len(q[0])]-=1
    q.popleft()
  
while q:                           #큐에 남은 이름을 같은 방법으로 처리해준다
  ans = ans + namelen[len(q[0])] - 1
  namelen[len(q[0])]-=1
  q.popleft()

print(ans)

for문과 while문을 합칠 수 있을 것 같지만 그냥 날 것 그대로의 코드로 남겨두어야겠다