2568번 - 전깃줄 - 2

1️⃣ 가장 긴 증가하는 부분순열

 

✏️ 풀이 과정

주어진 조건을 특정한 시선에서 바라보면 가장 긴 증가하는 부분순열(LIS)문제로 볼 수 있습니다. 즉 A와 B 중 하나를 인덱스, 그리고 나머지 하나를 값으로 보고 LIS 알고리즘을 적용하면 문제가 해결됩니다.

 

입력은 순서와 관계없이 들어오기 때문에 먼저 입력부터 정렬할 필요가 있습니다. 아래 풀이에서와 같이 A를 인덱스로 쓰기 위해서는 A를 기준으로 오름차순으로 정렬해야 합니다.

 

정렬 이후에는 문제가 한 가지 생기는데 A의 값을 1부터 순서대로 주는 것이 아니기 때문에 중간 중간이 비어 있어 A의 값을 그대로 인덱스로 쓸 수는 없습니다. 반면 LIS 알고리즘에는 0부터 시작하는 인덱스가 필요하기 때문에 우선 A의 값이 아닌 인덱스를 기준으로 삼아서 LIS 알고리즘을 실행하고 결과를 출력할 때 값을 가져와야 합니다.

 

O(NlogN)시간 내에 해결해야 하기 때문에 이분탐색을 사용하는 LIS 알고리즘을 사용해야 합니다. 또한 내용을 모두 복원해야하기 때문에 끝에서부터의 추적에 사용되는 trace배열과 직전 수를 저장하는 prev 배열이 필요합니다.

 

문제에서 요구하는 것은 찾은 수열이 아니라 그 수열을 제외한 나머지 부분(제거해야 될 전깃줄)이므로 N크기의 boolean형 배열을 만들어 수열에 포함 여부를 표시하고 제거할 지점들을 복원해야 합니다. 이 때 인덱스를 그대로 사용하는 것이 아니라 A값을 가져와야 하는 것을 주의하고 개수와 내용을 출력하면 문제가 해결됩니다.

 

⏱ 시간 복잡도

이분탐색을 사용하는 LIS 알고리즘이 사용되기 때문에 시간 복잡도는 O(NlogN)입니다.

 

💻 코드

Java

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

public class Main {

	static class Line implements Comparable<Line> {
		int from;
		int to;
		
		public Line(int from, int to) {
			this.from = from;
			this.to = to;
		}

		@Override
		public int compareTo(Line o) {
			return this.from-o.from;
		}
	}
	
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        Line[] input = new Line[N];
        int[] arr = new int[N];
        for(int i=0;i<N;i++) {
        	st = new StringTokenizer(br.readLine());
        	input[i] = new Line(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        Arrays.sort(input);
        int[] LIS = new int[N];
        int[] trace = new int[N];
        int[] prev = new int[N];
        int size = 0;
        int pos;
        for(int i=0;i<N;i++) {
        	arr[i] = input[i].to;
        	pos = Arrays.binarySearch(LIS, 0, size, arr[i]);
        	if(pos >= 0) continue;
        	pos = -1 * (pos + 1);
        	LIS[pos] = arr[i];
        	trace[pos] = i;
        	if(pos != 0) {
        		prev[i] = trace[pos - 1];
        	}
        	if(pos == size) {
        		size++;
        	}
        }
        boolean[] exist = new boolean[N];
        int j = trace[size-1];
        for(int i=0;i<size;i++) {
        	exist[j] = true;
        	j = prev[j];
        }
        sb.append(N-size+"\n");
        int[] result = new int[N-size];
        int cnt = 0;
        for(int i=0;i<N;i++) {
        	if(!exist[i]) {
        		result[cnt++] = input[i].from;
        	}
        }
        Arrays.sort(result);
        for(int i=0;i<N-size;i++) {
        	sb.append(result[i]+"\n");
        }
        System.out.print(sb);
        br.close();
    }
}