[ 알고리즘 ] 백준 3078번 좋은친구

백준 3078번 좋은 친구

문제 링크

문제 접근

처음에는 단순히 큐를 이용해서 일일히 계산을 하면 되는 쉬운 문제라고 생각하고 시작했다.
정답이 나오는 단순한 코드는 금방 짤 수 있었지만, 제출결과 시간초과......

결국 계속해서 다른 방법을 도전하다가 다른 분의 코드를 봤는데, 어떻게 이런 생각을 하시고 풀었는 지 놀라울 따름.......... 🤭

1. 먼저 문자열의 길이는 2~20으로 주어졌으므로, 길이 20짜리 Queue 배열을 선언했다.

2. 이 후 문자열의 입력이 들어오는데 이 때, 문자열의 내용은 중요하지 않으므로 바로 길이를 계산한다.

3. 계산한 길이를 이용하여 앞에 선언한 큐 배열의 인덱스로 각 큐를 불러온다.

   • 불러온 큐가 Empty 이면 바로 큐에 넣어주고,
   • 그렇지 않다면 큐 안의 원소들을 앞에서부터 지금 들어온 입력값 - 큐의 맨앞의 원소값 > K 을 만족하면(지금 들어온 입력값과 좋은 친구가 아니면) 반복문을 돌면서 전부 poll 해준다. 이 후 , 큐의 남은 원소들의 갯수를 좋은 친구 쌍의 수에 추가해준다.
   • 이 후 지금 들어온 입력값은 해당 큐에 넣어주고, 이를 각 입력마다 반복한다.

아, count 는 long 으로 선언해야 정답을 맞출수 있다.

---

이러한 방식으로 푸셨는데, 나는 당연히 입력을 다받고 나서, 이를 이용해서 어떻게 풀지 만을 생각했는데, 이런 식으로 생각을 하는 게 참 대단한 것 같다. 나도 이런 다양한 접근 방식을 가질 수 있기를.................. :)

코드

package Algorithms;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * https://www.acmicpc.net/problem/3078
 * 백준 3078번 좋은 친구
 */
public class Baekjoon3078 {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        Queue<Integer>[] queues = new Queue[21];
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());


        for (int i = 0; i < 21; i++) {
            queues[i] = new LinkedList<>();
        }

        long count = 0;
        for (int i = 0; i < N; i++) {
            int length = br.readLine().trim().length();

            if(queues[length].isEmpty()){
                queues[length].offer(i);
            } else {
                while(i- queues[length].peek() > K){
                        queues[length].poll();
                        if(queues[length].isEmpty()){
                            break;
                        }
                }

                count += queues[length].size();
                queues[length].offer(i);
            }
        }


        System.out.println(count);
    }
}