[백준 2568번 Java] 전깃줄 - 2

문제 난이도

PLATINUM V (문제 링크)

 

 

풀이

LIS 알고리즘을 이진 탐색을 통해 구현하면 되는 문제로 해당 문제를 어떻게 코드로 풀어낼 것인지에 대한 아이디어도 아래 포스팅에서 자세히 다루기 때문에 구체적인 설명은 필요하지 않을 것 같다.

[알고리즘] LIS (Longest Increasing Subsequence)

 

 

간단하게 복기하자면, 해당 문제는 전깃줄의 개수가 최대 100,000개이기 때문에, DP로 LIS를 구현해서는 풀 수가 없다.

 

 

전깃줄의 시작지점을 오름차순으로 정렬하면, 전깃줄의 끝나는 지점이 오름차순일 때, 즉 부분 LIS 가 서로 교차하지 않는 전깃줄이 된다.

이진 탐색을 통해, 전깃줄의 끝나는 지점의 위치들을 찾아 이를 전깃줄이 시작하는 지점의 위치와 만족하는 경우를 찾으면 된다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;

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());
        int[][] line = new int[N][2];

        for (int i = 0; i < N; i ++) {
            //99%에서 오답이 나는 경우가 있어 입력 라인에 공백을 제거해야했다.
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            line[i][0] = Integer.parseInt(st.nextToken());
            line[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(line, (o1, o2) -> o1[0] - o2[0]);
        ArrayList<Integer> l = new ArrayList<>();
        int[] lIdx = new int[N];

        for (int i = 0; i < N; i ++) {
            lIdx[i] = binarySearch(l, line[i][1]);
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int len = l.size();
        bw.write(N - len + "\n");

        HashSet<Integer> set = new HashSet<>();
        for (int i = N - 1, k = len - 1; i >= 0 && k >= 0; i--) {
            if (lIdx[i] == k) {
                set.add(line[i][1]);
                k--;
            }
        }

        for (int i = 0; i < N; i++) {
            if (!set.contains(line[i][1])) {
                bw.write(line[i][0] + "\n");
            }
        }

        bw.flush();
        bw.close();
    }

    private static int binarySearch(ArrayList<Integer> l, int endLine) {
        int start = 0;
        int end = l.size();

        while(start < end) {
            int mid = (start + end) / 2;

            if (l.get(mid) >= endLine) {
                end = mid;
            }
            else {
                start = mid + 1;
            }
        }

        if (start >= l.size()) {
            l.add(endLine);
        }
        else l.set(start, endLine);

        return start;
    }
}