[BaekJoon] 2568번 전깃줄 - 2 (Java) 문제 풀이 [Platinum 5]

문제

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

2568번: 전깃줄 - 2

 

어떻게 풀 것인가?

문제를 천천히 읽어보자.

두 전봇대 사이 A와 B에서 교차를 하면 안된다.

여기서 단순 구현이라기엔 시간제한 1초이며, 주어진 데이터(전깃줄의 개수)는 100,000 이하의 자연수이다.

브루트포스로 푼다면 1초를 훌쩍 넘긴다.

 

문제에서 주어진 두 전봇대에 주어진 숫자를 하나의 기준으로 정렬을 해본다면, 인덱스와 값이 보인다.

 

즉, 가장 긴 오름차순 수열이 아닌 것들을 제외하면 정답이 된다. 이 문제는 LIS ( Longest Increase Subsequence) 문제이다.

사실, 이러한 문제들을 바로 보고 떠올리기는 어렵다. 나도 최근에 LIS에 대해서 공부를 하였기에 운이 좋게도 빨리 풀 수 있었다.

https://superohinsung.tistory.com/199

[Algorithm] LIS, LDS (최장 증가 부분 수열, 최장 감소 부분 수열)

 

앞에서도 말했듯 시간 복잡도 때문에 O(N^2)가 발생할 경우 시간초과가 발생하게 된다.

 

그렇다면 O(N log N)의 시간복잡도를 가진 이분탐색 방법을 사용하여야 한다.

 

자 그렇다면

1. 한 쪽 전봇대(A 기준)를 오름차순으로 정렬한 뒤
2. 최대 LIS 요소가 아닌 전깃줄들을 제거한다.
3. 단, 현재 전깃줄이 자기가 속한  LIS의 몇번째 요소인지 저장해야한다. 각 요소가 항상 LIS를 이루지는 않기 때문이다.
4. 마지막으로 번호가 작은 전깃줄부터 출력해야하므로 Stack을 이용한다.

 

풀면서 놓쳤던점

두개의 전봇대라는 점에서 맨 처음에 코드로 구현하는 아이디어가 잘 떠오르지 않았다.

 

이 문제를 통해 얻어갈 것

LIS 활용법

 

내 코드 

package baekjoon4.BJ_2568;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;
import java.util.StringTokenizer;

// 백준알고리즘 2568번 전깃줄 - 2
class Wire implements Comparable<Wire> {
    int a;
    int b;

    Wire(int a, int b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public int compareTo(Wire o) {
        return a - o.a;
    }
}

public class Main {
    static int N;
    static StringBuilder sb;
    static ArrayList<Wire> wires;
    static ArrayList<Integer> list;
    static int[] checkIndex;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        sb = new StringBuilder();
        StringTokenizer st;
        wires = new ArrayList<>();
        list = new ArrayList<>();
        list.add(0);
        checkIndex = new int[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int one = Integer.parseInt(st.nextToken());
            int second = Integer.parseInt(st.nextToken());
            wires.add(new Wire(one, second));
        }

        Collections.sort(wires);

        sb.append(binarySearch()).append("\n");
        removeWire();
        System.out.print(sb);

    }

    public static int binarySearch() {

        for (int i = 0; i < N; i++) {
            if (list.get(list.size() - 1) < wires.get(i).b) {
                list.add(wires.get(i).b);
                checkIndex[i] = list.size() - 1;
            } else {
                int left = 1;
                int right = list.size() - 1;

                while (left < right) {
                    int mid = (left + right) / 2;
                    if (list.get(mid) < wires.get(i).b) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                list.set(right, wires.get(i).b);
                checkIndex[i] = right;
            }
        }
        return N - (list.size() - 1);
    }

    static void removeWire() {
        int index = list.size() - 1;
        Stack<Integer> stack = new Stack<>();
        for (int i = N - 1; i >= 0; i--) {
            if (checkIndex[i] == index) {
                index--;
            } else {
                stack.push(wires.get(i).a);
            }
        }

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

 

참고

X