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

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

 

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

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

---

1.  아이디어

 

이전 전깃줄 문제에서 전깃줄의 개수와 위치 번호가 늘어난 문제로 O(N^2) 시간복잡도의 다이나믹 프로그래밍으로는 해결할 수 없다. 이를 위해 이분 탐색을 활용한 LIS로 구현했고 해당 전깃줄을 포함하는 LIS의 길이를 저장하는 before 배열을 활용했다.([코딩테스트 준비/백준] - [백준] 2565번 - 전깃줄 [Java])

---

2. 문제풀이

 

이전 전깃줄 문제에서 LIS 로직만 이분 탐색을 활용하도록 바꿨다. dp 배열에는 Lower Bound 이분 탐색으로 수열의 해당 수가 들어갈 수 있는 위치를 반환하게 해서 dp 배열을 해당 수로 갱신시켰다. dp 배열은 인덱스 숫자와 같은 길이의 LIS의 마지막 원소가 저장된다. 추가로 before 배열로 해당 수열의 원소가 dp 배열에 저장된 인덱스를 저장했다.

 

이후 before 배열을 역순으로 돌며 len과 일치하는 값을 찾으면 해당 수열에서 해당 인덱스의 원소는 LIS의 마지막 원소가 된다. len - 1을 한 후 다시 len과 일치하는 원소를 찾으면 해당 원소는 LIS의 마지막 원소 이전 원소가 된다. 이렇게 역순으로 LIS를 구할 수 있고 Stack을 활용해 push한 후 pop을 하면 정배열의 LIS를 구할 수 있다. 해당 문제는 전깃줄을 없애야 하는 즉, LIS가 아닌 수들을 구해야하므로 len과 before 값이 일치하지 않으면 Stack에 넣는 과정을 반복하다가 일치하면 Stack에 넣지 않고 len - 1을 해줘서 LIS가 아닌 수들만 Stack에 넣도록 구현했다.

---

3. 코드

 

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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        // 0열은 A 전봇대의 위치, 1열은 B 전봇대의 위치
        int[][] map = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            map[i][0] = Integer.parseInt(st.nextToken());
            map[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(map, ((o1, o2) -> Integer.compare(o1[0], o2[0])));

        int[] dp = new int[1 + N];

        int[] before = new int[N];

        int len = 0;
        for (int i = 0; i < N; i++) {
            int idx = binarySearchLowerBound(dp, len, map[i][1]);
            dp[idx] = map[i][1];
            if (idx == len + 1) len++;

            before[i] = idx;
        }

        sb.append(N - len).append("\n");

        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = N - 1; i >= 0; i--) {
            if (before[i] != len) {
                stack.push(map[i][0]);
                continue;
            }

            len--;
        }

        while (!stack.isEmpty()) {
            sb.append(stack.pop()).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }

    // arr[]에서 target 이상인 가장 작은 원소의 인덱스를 반환하는 Lower Bound 이분 탐색
    private static int binarySearchLowerBound(int[] arr, int len, int target) {
        int left = 1;
        int right = len + 1;

        while (left < right) {
            int mid = (left + right) / 2;

            if (arr[mid] < target) left = mid + 1;
            else right = mid;
        }

        return right;
    }

}

---

4. 후기