[코딩테스트][백준] 🔥 백준 13334번 "철로" 문제: Java으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Java 풀이시간: 40분

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        int n= Integer.parseInt(st.nextToken());

        PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->Integer.compare(a[1],b[1]));

        for(int i=0;i<n;i++){
            st=new StringTokenizer(br.readLine());
            int h=Integer.parseInt(st.nextToken());
            int o=Integer.parseInt(st.nextToken());
            if(h<o){
                pq.offer(new int[]{h,o});
            }else{
                pq.offer(new int[]{o,h});
            }
        }

        st=new StringTokenizer(br.readLine());
        int d=Integer.parseInt(st.nextToken());

        int max=0;
        PriorityQueue<Integer> pq2=new PriorityQueue<>();
        while(!pq.isEmpty()){
            int[] now=pq.poll();
            int start=now[1]-d;
            pq2.offer(now[0]);
            while(!pq2.isEmpty()&&pq2.peek()<start){
                pq2.poll();
            }
            max=Math.max(max,pq2.size());
        }
        System.out.println(max);
    }
}

🚄 최적의 철로 배치: 포함된 선분의 최대 개수 구하기

철로를 놓을 때, 양 끝이 o와 h인 선분이 가장 많이 포함되었을 때의 그 포함된 갯수를 구하는 문제이다.

우선 아이디어의 추론은 다음과 같다. 우리가 이동시키면서 포함시켜야 하는건 고정되어 있는 d라는 길이 이기 때문에 이 길이를 그림 상에서 오른쪽으로 이동시키면서 포함되고 빠지는 경우를 따지는 것이다. 그렇되었을 때를 구하는 것인데 이 때, 우선순위 큐를 사용하면 간단하다.

철로를 하나씩 따지기는 하는데 우리는 오른쪽으로 이동하므로 가장 왼쪽에 있는 선분이 직관적으로 필요하다. 그렇기 때문에 우리는 끝점이 가장 왼쪽에 있는, 즉 가장 작은 선분을 가져오는 것이다. 선분을 가져오면 그 끝점에서 -d를 해주게 되면 현재 선분이 해당 선분을 끝을 맞추어서 놓여져 있는 상태와 같다. 그 상태로 현재 시점에서 벗어나버린 선분들을 큐에서 빼버리면 된다. 즉 이미 포함되버린 선분들 중에서 시작점보다 작은 선분들을 전부 제외시키면 된다. 그 때의 우선순위 큐에 담겨 있는 선분들의 갯수를 구하면 해당 영역에 포함되어 있는 선분의 수가 된다.

이렇게 Java으로 백준의 "철로" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊