글 읽기 - binarySearch 질문 이요~!

chlwlsgur000 1년 전 0

dp에서 index를 얻은 다음 그 index를 numbers에 이용하여

6
10 20 10 30 20 50

4
10 20 30 50

로 결과를 내고싶은데

System.out.println(numbers[ Arrays.binarySearch(dp, 4)]); = 50 // 정상 출력 됨

System.out.println(numbers[ Arrays.binarySearch(dp, 3)]); = -6 // 30을 기대했으나 -6이 출력이 되어 numbers배열에서 오류가 남

System.out.println(numbers[ Arrays.binarySearch(dp, 2)]); = 20 // 정상 출력 됨

System.out.println(numbers[ Arrays.binarySearch(dp, 1)]); =10 // 정상 출력 됨.

3을 제외하고 나머지 4,2,1은 정상출력이 되는데 왜 3만 안될까요.??

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

public class Main {
	 public static int dp[];
	 public static int numbers[];
	 public static void main(String[] args) throws NumberFormatException, IOException {
		     
		 BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		 Stack <Integer> stack = new Stack<>();

		      
		     
		 int N = Integer.parseInt(bf.readLine());
		 dp = new int[N];
		 numbers = new int[N];
		      
		 StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
		      
		 for(int i  = 0; i < N ; i++) {
		      numbers[i] = Integer.parseInt(st.nextToken()); 
		      dp[i] = 1;
		 }
		 
	
		 int ans = length(N);
		 System.out.println(ans);
		 
		 for(int i = 0 ; i < N; i++) {
			 System.out.print(dp[i] + " ");
		 }
		 System.out.println();
	
//-------------문제의 코드는 39------------------정상 값으로 30이 나와야 하는데   -6 이 나옴 -----------------
	System.out.println(numbers[ Arrays.binarySearch(dp, 3)]);
	
		 for(int i = ans ; 1 <= i ; i--) {
			 stack.push(numbers[ Arrays.binarySearch(dp, i)]);
		 }
		 
		 int a = stack.size();
		 
		 for(int i  = 0 ; i < a; i++) {
			 System.out.print(stack.pop() + " ");
		 }

	 }
	 public static int length(int n) {
	
		for(int j = 1; j < n; j++) { 
		
			for(int i = 0 ; i < j ; i++) {
				
		if(numbers[i] < numbers[j] && dp[j] < dp[i] + 1 ) {
			 dp[j] = dp[i] + 1;
		
		}
		
		}
	
			
	}
	int max = -1;
	for(int i = 0 ; i < n; i++) {
		if(max < dp[i]) {
			max = dp[i];
		}
	}
		
		
		 return max;
	 }
}

DP[i] = (i번째 위치에서 끝나는 부분수열 중 가장 긴 LIS 길이)인 것 같습니다. 예제 입력에 대해서는 DP[i] = {1, 2, 1, 3, 2, 4}입니다. DP[i]가 단조증가가 아니기 때문에 이분탐색을 사용할 수 없습니다. DP 값 역추적이 필요합니다. DP[i]가 최대인 i를 아무거나 찾고, 그 DP[i] 값을 준 j<i를 찾고, 이렇게 되짚어나가는 과정이 필요합니다. 구현은 두 가지로 가능합니다. 하나는 앞서 설명한 것처럼 i를 찾고 j<i를 찾기를 반복하면서 다시 계산해보는 방식이고, 다른 하나는 DP표를 채울 때 argmax를 저장해놓는 것입니다.

chlwlsgur000 1년 전 0

네. 댓글 감사합니다! 다시 역추적으로 문제를 풀어서 맞추긴 했는데 왜

System.out.println(numbers[ Arrays.binarySearch(dp, 3)]);

이 라인만 비정상적인 출력이 나오는지 궁금했습니다!

byeongkeunahn 1년 전 0

Java documentation을 보면 정확히 그 값이 존재하지 않는 경우 그 값보다 큰 최초의 위치를 j라고 할 때 -j-1이 반환되는 것으로 되어 있습니다.

chlwlsgur000 1년 전 0

네! 계속 댓글로 여쭤봐서 정말 죄송한데, 제가 구글링으로 binarySearch에 공부하고 왔는데

저 코드를 실행 해보면 dp배열이 { 1, 2, 1, 3, 2, 4} 이 나옵니다.

그래서 저는 당연히 dp배열에 요소값으로 3이 있으니

Arrays.binarySearch(dp, 3) 는 3이 나올 줄 알았는데 byeongkeunahn님 말씀대로 -6이 나오네요...

정말 컴퓨터 세계는 알다가도 모르는거 같습니다 ㅋㅋㅋㅋ

좀 더 공부해보겠습니다! 늦은 시간에 감사합니다!

chlwlsgur000 1년 전 0

아마 제생각에 dp배열이 정렬되지 않은 체 binarySearch를 사용하여 그런거같습니다!

byeongkeunahn 1년 전 0

네네 binarySearch에 정렬되지 않은 배열을 줘서 오작동하는 게 맞습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

binarySearch 질문 이요~!

chlwlsgur000 1년 전 0

byeongkeunahn 1년 전 0

chlwlsgur000 1년 전 0

byeongkeunahn 1년 전 0

chlwlsgur000 1년 전 0

chlwlsgur000 1년 전 0

byeongkeunahn 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말