ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [ 알고리즘 ] 백준 3078번 좋은친구
    프로그래밍/알고리즘 2019. 5. 3. 13:20

    백준 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);
        }
    }
    

    댓글 0

Designed by Tistory.