[백준 2568] - 전깃줄-2(JAVA)[플레5]

문제

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

2568번: 전깃줄 - 2

 

문제 풀이

 

본론부터 말하면 해당 문제는 LIS 알고리즘을 활용하는 문제이다.

왜 그렇게 생각했느냐에 대해서 얘기해볼까 한다.

 

우리의 목표는 A와 B를 연결하는 전깃줄이 교차하지 않게 하면서, 최소한의 전깃줄을 제거해야 한다.

 

그러면 전깃줄이 교차하는 경우는 무엇일까?

A의 1번은 B의 8번과 연결되어 있고, A의 2번은 B의 2번과 연결되어 있다.

A의 1번 전깃줄을 연결한 상태에서 A의 2번을 연결하려고 할 때, 교차가 발생하는 것을 알 수 있다.

즉 앞전에 연결한 전깃줄의 B값보다 작은 B값에 해당하는 전기줄을 연결하면 교차가 발생한다는 것을 알 수 있다.

A의 1번을 제외하고, A의 2번과 3번을 연결하면 A(2) -> B(2) , A(3) -> B(9)이기 때문에 교차가 발생하지 않는다.

 

즉 이러한 결과를 통해서 우리는 B의 값이 증가하는 수열을 구하면 된다.

 

그리고 우리는 최소한의 전깃줄을 없애야 하기 때문에 수열의 길이가 가장 큰 수열을 구하면 될 것이다.

LIS 문제는 여러 방법으로 풀 수 있지만, 해당 문제는 시간제한이 1초이고, 전깃줄의 개수가 최대 100,000개이기 때문에

N^2 알고리즘으로 해결할 수 없기 때문에 이분탐색(logn)을 이용해야 한다.

 

LIS 문제에서 이분탐색은 탐색하고자 하는 값이 들어갈 수 있는 최적의 위치를 반환해준다.

 public static int getCorrectIndex(int left, int right, int value) {
        int mid;
        while (left < right) {
            mid = (left + right) / 2;
            int cur = ary.get(mid).b;
            if (cur == value) { //같을 경우
                return mid;
            } else if (cur > value) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
}

 

해당 함수를 통해서 기존 수열에서 value가 들어갈 수 있는 최적의 위치를 반환해 줍니다.

예를 들어서 {2,4}가 있고, value가 1이라면 left는 0, value가 3이라면 left는 1이 반환될 것입니다.

n개의 원소를 통해서 증가하는 수열을 이분탐색으로 만들었다면 다음은 해당 수열을 정상적으로 만들어 줘야 합니다.

위에서도 말했던 것처럼 이분탐색은 value가 들어갈 수 있는 최적의 위치를 반환해 줍니다.

하지만 이렇게 만들어진 수열은 정확한 수열이 아닐 수도 있습니다.

 

{2,5,7,8,1}이라는 값을 통해서 수열을 만 들 경 우 이분탐색으로 인해 만들어진 수열은 최종적으로 {1,5,7,8}이 될 것입니다.

하지만 {1,5,7,8}은 정확한 수열이 아닙니다. 왜냐하면 1번은 5,7,8보다 뒤에 있기 때문입니다.

이와 같이 이분탐색으로 인해 만들어진 수열은 수열의 길이만 보장할 뿐, 원소의 값까지는 보장해주지 못합니다.

이를 위해서 저는 수열에 원소를 추가하거나, 변경할 때마다 index 배열을 통해서 해당 숫자의 기존 위치를 기록해 줬습니다.

index [1]은 4가 되고, index [2]는 0이 되겠죠.

우리는 이러한 index 배열을 통해서 해당 숫자가 수열에 적합한 숫자인지 아닌지를 판단할 수 있습니다.

   public static void adjustIndex() {
        int limit = ary.size() - 1;
        for (int i = 500000; i >= 0; i--) {
            if (lines[i] == null)
                continue;
            if (index[i] == limit) {
                limit -= 1;
            } else {
                result.add(lines[i].a);
            }
        }
 }

• limit를 최종적인 수열의 크기로 잡고, 뒤에서부터 찾아줍니다.
• i의 index 값이 limit와 동일하다면 i라는 원소는 수열에 적합한 원소입니다.
  • 적합하다면 limit를 감소시켜 줍니다. 다음 위치에 원소를 찾아야 하기 때문입니다.
• 우리가 구하고자 하는 원소는 잘라내야 하는 원소들이기 때문에 적합하지 않은 원소들은 모두 result 배열에 넣어줍니다.

해당 코드의 결과로 result 배열에는 자르는 전깃줄의 위치가 들어갈 것입니다.

전체 코드

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

public class Main {

    static BufferedReader br;
    static StringTokenizer st;

    static int n;

    static Line[] lines = new Line[500001];

    static ArrayList<Line> ary;

    static ArrayList<Integer> result = new ArrayList<>();

    static int[] index = new int[500001];

    public static void main(String[] args) throws IOException {
        input();
        connection();
        adjustIndex();
        answer();
    }

    public static void answer() {
        System.out.println(n - ary.size());
        for (int i = result.size() - 1; i >= 0; i--) {
            System.out.println(result.get(i));
        }
    }

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        ary = new ArrayList<>();
        int a, b;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            lines[a] = new Line(a, b);
        }
    }


    public static void connection() {
        for (int i = 0; i < 500001; i++) {
            if (lines[i] == null)
                continue;
            if (ary.size() == 0 || ary.get(ary.size() - 1).b < lines[i].b) {
                ary.add(lines[i]);
                index[lines[i].a] = ary.size() - 1;
            } else {
                int idx = getCorrectIndex(0, ary.size() - 1, lines[i].b);
                ary.set(idx, lines[i]);
                index[lines[i].a] = idx;
            }
        }
    }


    public static int getCorrectIndex(int left, int right, int value) {
        int mid;
        while (left < right) {
            mid = (left + right) / 2;
            int cur = ary.get(mid).b;
            if (cur == value) { //같을 경우
                return mid;
            } else if (cur > value) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public static void adjustIndex() {
        int limit = ary.size() - 1;
        for (int i = 500000; i >= 0; i--) {
            if (lines[i] == null)
                continue;
            if (index[i] == limit) {
                limit -= 1;
            } else {
                result.add(lines[i].a);
            }
        }
    }

    public static class Line {
        int a, b;

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