[BOJ] 3078 - 좋은 친구

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

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

3078번: 좋은 친구

난이도: 골드 3

사용언어: JAVA

 

풀이

문제를 해결하는 여러 방법이 있겠지만, 저는 큐를 이용하여 문제를 풀었습니다. 

 

문제 해결 방법은 다음과 같습니다.

 

1. 한 명씩 입력을 받으며 큐에 삽입한다.

2. 등수의 차이가 K를 벗어나면 큐에서 삭제한다. (큐 내부에는 등수가 K 이내인 친구만 존재한다)

3. 입력을 받은 이름과 같은 길이의 이름이 큐에 몇 개가 남아있는지 체크하여 좋은 친구의 수를 구한다.

 

참고로 정답의 최댓값이 300000 * 299999 / 2로 Int형의 크기를 벗어나기 때문에 Long 타입으로 선언한 변수를 활용해야 합니다.

 

다음은 제가 작성한 코드입니다.

 

import java.util.*;
import java.io.*;
 
public class Main {
 
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        long cnt = 0;
        Queue<String> q = new LinkedList<>();
        long[] name_length = new long[21]; // K명 안에 이름 길이 별로 친구가 몇명이 있는지
        for (int i = 0; i < N; i++) {
            String now = br.readLine();
 
            if (name_length[now.length()] > 0) {
                cnt += name_length[now.length()]; // 이름 길이에 맞춰 좋은 친구의 수를 합산
            }
 
            q.add(now); // Queue에 넣고
            name_length[now.length()]++; // 배열도 수정
 
            if (q.size() > K) { // K등 이상이 차이가 나는 사람에 대해
                name_length[q.poll().length()]--; // Queue에서 삭제 및 배열 수정
            }
        }
 
        bw.write(String.valueOf(cnt));
        bw.flush();
        bw.close();
        br.close();
    }
}