[Java] 백준 2565번: 전깃줄

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

2565번: 전깃줄

 

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
	private static int bisectLeft(ArrayList<Integer> nums, int value) {
		int left = 0;
		int right = nums.size()-1;
		int mid;
		
		while(left<=right) {
			mid = (left + right)/2;
			if(nums.get(mid) >= value) {
				right = mid-1;
			}else {
				left = mid+1;
			}
		}
		
		return left;
	}
	
	private static int solution(int[][] nums, int N) {
		int i, j;
		int index;
		Arrays.sort(nums, (o1, o2) -> o1[0] - o2[0]);
		
		// LIS
		ArrayList<Integer> stack = new ArrayList<Integer>();
		int stackLength = 0;
		for(i=0;i<N;i++) {
			index = bisectLeft(stack, nums[i][1]);
			
			if(index >= stackLength) {
				stack.add(nums[i][1]);
				stackLength += 1;
			}else {
				stack.set(index, nums[i][1]);
			}
		}
		
		return N - stackLength;
	}
	
	public static void main(String[] args) {
		int i;
		Scanner sn = new Scanner(System.in);
		int N = sn.nextInt();
		
		int[][] nums = new int[N][2];
		for(i=0;i<N;i++) {
			nums[i][0] = sn.nextInt();
			nums[i][1] = sn.nextInt();
		}

		System.out.println(solution(nums, N));
	}
}

 

예제 입력 1에서 전봇대 A를 기준으로 정렬하면 다음과 같다.

1 8
2 2
3 9
4 1
6 4
7 6
9 7
10 10

 

이 상태에서 전봇대 B의 LIS를 구하면, 그것이 서로 교차하지 않았을 때의 최대 전깃줄의 갯수이다. 즉 N - (LIS의 길이)를 해주면 된다.

LIS 관련 설명은 다음 링크에 있으니 참고하자.

https://rccode.tistory.com/entry/14003

[Python] 백준 14003번: 가장 긴 증가하는 부분 수열 5