[백준] 13334: 철로 (우선순위 큐 활용하기) - JAVA

class 6

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

 

 

 

# 문제

 

 

# 필요개념

배열에 담아서 정렬하면 편한 문제겠지만 시간이 1초라서 O(n^2) 가 되면 시간초과가 발생한다. 혹시나 해봤지만 역시나이니 시도하지 않아도 된다.

 

이렇게 일정 간격을 순회해야 할 경우 투포인터를 응용하여 문제를 풀 수 있다.

 

이 문제는 일정 간격(dis) 안에 집과 회사가 모두 들어있는 루트의 개수를 구해야 하는 문제이다. 푸는 기본적인 로직은 다음과 같다.

• 입력받은 수를 저장할 이차원 배열과 실제 문제풀이에 이용할 리스트를 각각 생성한다.
• 숫자 두개를 입력받되, 작은 것을 집, 큰 것을 회사라고 가정한다. 입력을 받을 때 작은 숫자가 앞에 오지 않는 경우도 있기 때문에 애초에 배열에 저장할 때 min과 max 함수를 이용하여 (작은수, 큰수) 로 저장해둔다.
• 집과 회사의 거리 (work - home) 이 주어진 간격(dis)보다 크면 어짜피 정답이 될 수 없다. 이 경우는 리스트에 저장하지 않는다. 
• 리스트를 정렬해야한다. 이때 정렬하는 방법이 중요하다.

 

✅ 첫 시도 - home을 기준으로 오름차순 정렬

처음에는 집을 기준으로 오름차순 정렬을 한 후, for문 해당 집 + 간격 보다 회사가 클 떄까지 돌렸다. 

 

그런데 이렇게 하면 반례가 생긴다.

3
1 4
2 5 
3 4
3

 

입력이 이렇게 주어지면, 첫 노드인 1,4 에서 뒤를 탐색할 때, limit은 4가 되므로 2,5에서 break가 걸린다.

저 부분을 개선해도 이중 for문이라 시간초과가 발생한다.

 

 

✅ 두번째 시도 - work를 기준으로 오름차순 정렬 후 start값을 PriorityQueue에 저장

비슷한 유형의 문제를 풀 때 시간을 확 줄일 수 있는 방법일 거 같다. home과 work는 home <= work가 성립되도록 저장해두었기 때문에, work를 기준으로 정리해도 괜찮다.

 

그럼 위 반례의 경우 아래와 같이 정렬된다.

1 4
3 4
2 5

 

work - dis 보다 크거나 같은 값을 가진 값만 Queue에 남기고 마지막에 큐의 size를 출력하면 정답을 구할 수 있다.

즉, peek()의 work - dis보다 home이 작으면 poll() 해준다. 이를 while문으로 돌리면 된다.

 

다 빼낸 후에는 현재 노드의 start를 넣어준다. 어짜피 work - start <= dis 인 노드만 리스트에 저장되어있기 때문에 그냥 넣어주어도 괜찮다.

정답코드의 key

 

 

# Code

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

import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        List<Node> lst = new ArrayList<>();
        long[][] input = new long[N][2];
        for (int i = 0 ; i < N ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long home = Long.parseLong(st.nextToken());
            long work = Long.parseLong(st.nextToken());
            input[i][0] = min(home, work);
            input[i][1] = max(home, work);
        }
        long dis = Long.parseLong(br.readLine());
        for (int i = 0 ; i < N ; i++) {
            if (input[i][1] - input[i][0] <= dis) lst.add(new Node(input[i][0], input[i][1]));
        }
        if (lst.isEmpty()) {
            System.out.println(0);
            return;
        }
        Collections.sort(lst, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return (int) (o1.work - o2.work);
            }
        });
        long max = 0;
        Queue<Long> queue = new PriorityQueue<>();
        for (int i = 0 ; i < lst.size() ; i++) {
            long end = lst.get(i).work;
            long start = end - dis;
            while (!queue.isEmpty() && queue.peek() < start) {
                queue.poll();
            }
            queue.add(lst.get(i).home);
            max = max(max, queue.size());
        }
        System.out.println(max);
    }
}
class Node {
    long home;
    long work;
    Node(long h, long w) {
        this.home = h;
        this.work = w;
    }
}

 

 

# 결과