백준 2568번 전깃줄 - 2 (JAVA)

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

2568번: 전깃줄 - 2

 

저는 해당 문제를 LIS와 링크드 리스트(?) 개념을 활용하여 문제를 해결하였습니다.

먼저 LIS를 binarySearch를 활용하여 시간복잡도를 nlog(n)으로 해결하였습니다. 

LIS 앍고리즘을 진행하면서 prev를 초기화해주었습니다. prev는 해당 값이 나오기 이전에 무슨 값이였는지를 저장하였습니다.

lis의 마지막 값에서 prev가 0이 나올때까지가 LIS의 최장 수열이기에 이를 제외하고 출력하였습니다.

 

 

 

package BOJ.DP;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_2568 {
    private static final int SIZE =  500_000;
    private static class Node{
        int a;
        int b;

        public Node(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(br.readLine());
        Node[] input = new Node[n];
        int[] lis = new int[n];
        int[] prev = new int[SIZE+1];
        boolean[] used = new boolean[SIZE+1];
        for(int i = 0 ; i < n ; i++){
            st = new StringTokenizer(br.readLine());
            int a = stoi.apply(st.nextToken());
            int b = stoi.apply(st.nextToken());
            input[i] = new Node(a,b);
        }
        Arrays.sort(input, (o1,o2)->{
           return o1.a - o2.a;
        });
        int size = 0;
        for(int i = 0 ; i < n ; i++){
            int b = input[i].b;
            int index = Arrays.binarySearch(lis,0,size,b);
            index = -index -1;
            lis[index] = b;
            if(index > 0){
                prev[b] = lis[index-1];
            }
            if(index == size){
                size++;
            }
        }
        System.out.println(n - size);
        int index = lis[size-1];
        while(index > 0){
//            System.out.println(index);
            used[index] = true;
            index = prev[index];
        }
        for(int i = 0 ; i < n ; i++){
            if(!used[input[i].b]){
                System.out.println(input[i].a);
            }
        }
    }
}