📌 서론.

📚 오늘의 문제.

📝 문제 1.

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

1. 문제 설명

   상근이네 반 학생의 이름이 성적순으로 주어지면, 이름 길이가 같고, 등수 차이가 k보다 작거나 같은 친구 쌍을 구하는 문제이다.

   

2. 문제 풀이

   • 두 개의 인덱스(start, end)를 활용한 풀이 (시간초과)

     import java.io.*;
     
     public class Main {
         public static void main(String[] args) throws IOException {
     
             BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
     
             String[] input = br.readLine().split(" ");
             int n = Integer.parseInt(input[0]);
             int k = Integer.parseInt(input[1]);
             int answer = 0;
     
             String[] array = new String[n];
             for (int i = 0; i < n; i++) {
                 array[i] = br.readLine();
             }
     
             int start = 0;
             int end = 1;
             while (start <= n - k) {
                 if (end - start <= k) {
                     if (array[start].length() == array[end].length()) {
                         answer += 1;
                     }
                     end += 1;
                 } else {
                     start += 1;
                     end = start + 1;
                     continue;
                 }
     
                 if (end >= n) {
                     start += 1;
                     end = start + 1;
                 }
             }
     
             bw.write(String.valueOf(answer));
             br.close();
             bw.close();
         }
     }

• Queue를 활용한 풀이 (Passed)
  • 들어오는 학생을 기준으로 큐 안에 자신과 쌍을 이룰 수 있는 친구가 있는지 찾는 방식으로 풀이
  • 이름 길이를 기준으로 큐를 분류하여 큐마다 아래 로직을 수행할 수 있도록 함
  • 기본적으로 arr[len].peek() (맨 앞에 있는 친구)와 나의 등수가 k이하이면, 큐 안에 있는 모든 친구들과 나는 좋은 친구가 될 수 있다는 아이디어를 전제로 한다.

  1. i=1, arr[3].isEmpty → IVA 입장에서 자신과 좋은 친구를 맺을 친구가 없음 → answer += 0 → IVA 삽입

     

  2. i=2, arr[3].size() = 1 → IVO와 제일 처음 들어온 친구(IVA)의 등수 차이가 k 이하임 → 큐에 있는 친구와 좋은 친구를 맺을 수 있음! → answer += 1 → IVO 삽입

     

  3. i=3, arr[3].size() = 2 → ANA와 제일 처음 들어온 친구(IVA)의 등수 차이가 k 이하임 → 큐에 있는 친구들과 좋은 친구를 맺을 수 있음! → answer += 2 → ANA 삽입

     

  4. i=3, arr[3].size() = 3 → TOM과 제일 처음 들어온 친구(IVA)의 등수 차이가 k 초과됨! → 그럼 우선 IVA와는 좋은 친구를 맺을 수 없음! → arr[3].poll()하면서 나와 좋은 친구를 맺을 수 있는 친구가 있을 때까지 진행함 → 큐에 남아 있는 친구들과 좋은 친구를 맺을 수 있음! → answer += 2 → TOM 삽입

     

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int k = Integer.parseInt(input[1]);
        long answer = 0;

        // 이름 길이 별로 큐 생성
        Queue<Integer>[] arr = new Queue[21];
        for (int i = 0; i <= 20; i++) {
            arr[i] = new LinkedList<>();
        }

        for (int i = 1; i <= n; i++) {
            String name = br.readLine();
            int len = name.length();

            // 큐가 비어 있지 않고 현재 인덱스와 맨 앞 인덱스의 차이가 k보다 크면 큐에서 제거
            while (!arr[len].isEmpty() && i - arr[len].peek() > k) {
                arr[len].poll();
            }

            // 현재 큐에 남아 있는 모든 요소는 i와 짝을 이룰 수 있음
            answer += arr[len].size();

            // 현재 인덱스를 큐에 추가
            arr[len].add(i);
        }

        bw.write(String.valueOf(answer));
        br.close();
        bw.close();
    }
}

🎯 결론.

골드 문제 정도 되니까 문제를 푸는 것보다는 시간 복잡도를 고려해서 문제를 푸는 아이디어를 떠올리는 게 어려운 것 같다. (사실 아이디어를 떠올리기가 어려워서 검색 도움을 받았다 🥲) 반복적인 풀이를 통한 복습이 중요할 것 같다.