[BOJ 2568] 전깃줄 2 - JAVA, Platinum5

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

2568번: 전깃줄 - 2

 

사용한 알고리즘 : LIS, 이진탐색

 

풀이 전략

위 문제에서 주어진 예제를 그대로 사용할 때, 앞 A 전봇대를 오름차순으로 정렬하고

B 전봇대를 기준으로 LIS를 구하면 [3,6,7,9,10] 이라는 결과가 나옵니다.

 

따라서 (처음 입력받은 전깃줄의 개수) - (LIS로 구한 배열의 크기)를 구해 제거해야 할 전깃줄의

개수를 구할 수 있습니다.

 

하지만 문제에서 제거해야할 전깃줄의 개수와 전깃줄의 번호를 구하라고 했기 때문에 추가적인 연산이

필요합니다.

 

이를 위해서는 LIS 연산을 수행할 때,  별도의 배열을 하나 더 추가하고

원본 수열의 개수를 하나씩 LIS 배열에 추가하는 과정에서,

추가되는 수가 LIS 배열에서 몇번째 칸에 들어가는지 저장해주면 됩니다.

 

그림으로 표현하면 아래와 같습니다.

이미지 출처: https://yhwan.tistory.com/21

 

그러면 Record 배열을 통해 LIS 배열에 수가 추가되어 들어갈 때, 몇번째 칸에 삽입되어 들어갔는지 알 수 있습니다.

Record 배열의 가장 뒤에서부터 순차적으로 내림차순의 배열을 구하면

LIS 배열의 역순이 출력되고, 이를 앞뒤 반전시키면 최종적인 LIS 배열을 구할 수 있게됩니다.

 

우리가 최종적으로 구하려는 배열은 삭제해야할 전봇대의 번호로,

모든 전봇대의 번호들 중, 위에서 구한 최종 LIS 배열과 중복되지 않는 번호를 출력하면 되겠습니다.

 

제출 코드

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

public class Main {

    static int N;
    static ArrayList<Node> d = new ArrayList<>();
    static ArrayList<Integer> result = new ArrayList<>();

    static int binarySearch(int start,int end,int target){

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

            if(result.get(mid)==target){
                return mid;
            }
            else if(result.get(mid)<target){
                start=mid+1;
            }
            else if(result.get(mid)>target){
                end=mid-1;
            }
        }
        return start;
    }

    static class Node implements Comparable<Node>{
        int start;
        int end;

        public Node(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Node o) {
            if(this.start<o.start) return -1;
            return 1;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

        for(int i=0;i<N;++i){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            d.add(new Node(a,b));
        }
        Collections.sort(d);

        ArrayList<Integer> indexBox = new ArrayList<>();
        result.add(d.get(0).end);
        indexBox.add(0);
        for(int i=1;i<N;++i){
            int index = binarySearch(0,result.size()-1,d.get(i).end);
            if(result.size()==index) result.add(d.get(i).end);
            else result.set(index,d.get(i).end);
            indexBox.add(index);
        }

        bw.write(N-result.size()+"\n");

        ArrayList<Integer> resultList = new ArrayList<>();
        int currentIndex=result.size()-1;
        for(int i=indexBox.size()-1;i>=0;--i){
            if(indexBox.get(i)==currentIndex){
                resultList.add(i);
                currentIndex--;
                if(currentIndex==-1) break;
            }
        }
        Collections.reverse(resultList);

        outter: for(Node node:d){
            for(int x:resultList){
                if(node.start==d.get(x).start) continue outter;
            }
            bw.write(node.start+"\n");
        }
        bw.flush();
        bw.close();
    }
}