좋은 친구 (3078번) - 백준 (BOJ)

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

3078번: 좋은 친구

 

 

백준 - 좋은 친구 (3078번) (MALCOLM)

 

난이도 : Gold 4

알고리즘&자료구조 : Queue (큐)

풀이 소요 시간 : 15 mins

Time Complexity : O( N )

 

 

import sys
input = sys.stdin.readline
from collections import deque


if __name__ == '__main__':
    N, K = map(int, input().split())
    q = deque()
    rem = [0] * 21
    pairs = 0
    for _ in range(K):
        x = len(input().rstrip())
        pairs += rem[x]
        rem[x] += 1
        q.append(x)
    for _ in range(N-K):
        x = len(input().rstrip())
        pairs += rem[x]
        rem[x] += 1
        q.append(x)
        rem[q.popleft()] -= 1
    print(pairs)

 

 

큐로 해결 가능한 문제이다.

 

초기화

 

좋은 친구 쌍을 저장할 "pairs"를 0으로 설정한다. ( pairs = 0 )

각 문자열의 길이가 2~20이므로, 길이가 21인 list "rem"을 만들어준다.

K명의 학생을 담아둘 list 큐 "q"를 만들어준다.

 

 

처음 K 개에 대해선 아래의 두 단계를 수행해준다.

 

① pairs에, rem[ 현재 문자열 길이 ] 값을 더해준다.

즉, 나보다 랭킹이 K단계 이하로 높은 "좋은 친구" 수를 더해준다.

( ex,  "IVA" → pairs += rem[3] )

 

② rem[ 현재 문자열 길이 ] 에 1을 더해주고,

( ex,  "IVA" → rem[3] += 1 )

현재 문자열 길이를 큐 (q) 에 추가한다. → q.append(x)

 

 

나머지 N-K 개는, 위의 ①, ② 단계 이후에
아래의  ③ 단계를 추가로 수행한다.

 

③ 랭킹이 K단계보다 더 높은 학생을 제거하고,

rem의 [ 해당 학생의 이름 길이의 index ] 에서, 1을 빼준다.

→ rem[q.popleft()] -= 1