전기줄 (정올 1257, 백준 2568)

문제링크

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=540&sca=99&sfl=wr_hit&stx=1257 

JUNGOL

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

2568번: 전깃줄 - 2

풀이 

이분탐색을 쓰지 않으면 시간초과 발생한다.

같은 숫자가 있으면 양수, 없으면 음수로 반환된다. 음수 idx는 -1 부터 시작

	0		1		2		3
1	2	3	4	5	7	8	9	10
-1		-2		-3		-4		-5

 

Arrays.binarySearch() 사용

 

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

public class Main {
	/*
	 * 전기줄2 
	 * https://www.acmicpc.net/problem/2565
	 * DP : 최장 증가 부분수열(LIS)
	 * 전기줄의 개수가 10^5
	 * 
	 * 
	 */
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		int n=Integer.parseInt(br.readLine());
		int[][] input=new int[n][2];
		StringTokenizer st;
		for(int i=0;i<n;i++) {
			st=new StringTokenizer(br.readLine());
			input[i][0]=Integer.parseInt(st.nextToken());
			input[i][1]=Integer.parseInt(st.nextToken());
		}//입력
		Arrays.sort(input,(o1,o2)->{
			return o1[0]-o2[0];
		});//a를 기준으로 정렬한다.
		
		int[] p=new int[500001];
		boolean[] flag=new boolean[500001];
		
		int[] arr=new int[n+1];//사용하는 전선을 보관할 스택
		Arrays.fill(arr, Integer.MAX_VALUE);//최기화
		int cnt=0;
		for(int i=0;i<n;i++) {
			int key=input[i][1];//햔재 전선의 b지점
			int idx=-(Arrays.binarySearch(arr,key)+1);
			/*
			 * 자바 이진탐색 라이브러리. 반드신 정렬된 데이터에서 사용.
			 * 찾고자 하는 값이 있으면 양수 idx, 없으면 -1부터 차례대로 출력된다.
			 * 		0 		1		2		3
			 * 1	2	3	4	5	7	8	9	10
			 * -1		-2		-3		-4		-5
			 */
			if(arr[idx]==Integer.MAX_VALUE) {
				cnt++;
			}//제일 끝에 추가됨으로
			arr[idx]=key;//교환 혹은 추가
			p[key]=idx==0?-1:arr[idx-1];//0이면 root 이기 때문에 -1
		}
		StringBuilder sb=new StringBuilder();
		int next=arr[cnt-1];
		while(next!=-1) {
			flag[next]=true;
			next=p[next];
		}//root까지 따라 올라가며 사용한 전선을 표시한다.
		
		sb.append((n-cnt)+"\n");
		for(int i=0;i<n;i++) {
			if(!flag[input[i][1]]) {
				sb.append(input[i][0]);
				sb.append("\n");
			}
		}//사용하지 않은 전선
		
		bw.append(sb.toString());
		bw.flush();
		bw.close();
	}

}