코딩테스트

[인프런 자바/java] 3. 최대 부분 증가수열 _디버깅의 눈물

디버깅의 눈물 2022. 9. 19. 16:27

체크 포인트

 

1. 다이나믹 프로그래밍(Dynamic Programming, 동적계획법)을 이용

-큰 문제를 여러 가지 작은 문제로 나누어 해결해보는 DP를 이용했다.

 

예를 들어, 예시 1의 경우

 

1)첫 번째 값의 부분증가수열의 최대길이 = 1

2)두 번째 값의 부분증가수열의 최대길이 = 1

2)세 번째 값의 부분증가수열의 최대길이 = 2

...

8)8 번째 값의 부분증가수열의 최대길이 = 2

 

를 가장 작은 경우의 수부터 구해보며 연산 과정을 추론하였다. 

 

 

2. 부분증가수열의 최대길이를 구하는 로직

 

예시 1의 경우, 아래와 같이 표현할 수 있다.

 

    	//  index = 1 2 3 4 5 6 7 8
    	// arr[N] = 5 3 7 8 6 2 9 4 (입력된 숫자)
    	//  dp[N] = 1 1 2 3 2 1 4 2 (부분증가수열 최대 길이)

 

문제의 답에 해당하는 dp[N]을 구하는 로직은,

 

1)dp 배열의 첫 번째 값(arr배열 첫번째 값의 부분증가수열 최대길이)은 무조건 1이다.

 

2)dp 배열의 두 번째 값부터

(1)arr 배열을 왼쪽 방향으로 모두 탐색하면서, 

(2)해당 arr[j]가 arr[i]보다 작은 숫자인 경우,

(3)arr[j]에 해당하는 dp[j]의 값 중에서 가장 큰 길이 + 1dp[i]의 값이 된다.

 

자세히 설명하자면,

dp[5]값을 구하기 위해서,

(1)arr[4], arr[3], arr[2], arr[1]을 모두 탐색하면서(arr[5] 기준 왼쪽 방향),

(2)해당 arr배열 값이 arr[5]보다 작다면(arr[2]=3, arr[1]=5는 arr[5]=6보다 작기 때문에 탐색 실시!) ,

(3)해당 dp배열 값 중에서 가장 큰 길이(dp[2]=1, dp[1]=1이므로, 1)에 1을 더한 값이 dp[5]의 값(2)이 된다.

 

마찬가지로 dp[7]의 경우,

(1)arr[6]부터 arr[1]까지 탐색하며,

(2)arr[7]인 9보다 작은 값을 가진 배열에 대한 dp배열 값 중,

(3)최대길이가 가장 큰 수(dp[4]=3)에 1을 더한 4가 dp[7]이 된다.

 

 

 

풀이

Bottom-up(바텀업)으로 해결

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public  class Main {
	
	// 입력되는 숫자를 담아주는 배열
	static int[] arr;
	
	// 동적 계획법 활용 배열
	static int[] dp;
	
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	// 입력되는 데이터의 수 N(3≤N≤1,000, 자연수)
    	int N = Integer.parseInt(st.nextToken());
    	
    	// 배열 초기화
    	arr = new int[N+1];
    	dp = new int[N+1];
    	
    	// 첫번째 값 초기화
    	// 하나의 값인 경우, 무조건 부분증가수열의 최대길이는 1이다.
    	dp[1] = 1;
    	
    	st = new StringTokenizer(br.readLine(), " ");
    	
    	// 받아온 숫자를 배열에 입력
    	for(int i=1; i<=N; i++){
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	// 예시 1의 경우,
    	//  index = 1 2 3 4 5 6 7 8
    	// arr[N] = 5 3 7 8 6 2 9 4 (입력된 숫자)
    	//  dp[N] = 1 1 2 3 2 1 4 2 (부분증가수열 최대 길이)
    	
    	
    	System.out.println(solution(N));
    	
    } // end of Main
    
    
    
    
    static int solution(int N) {
    	// bottom-up(바텀업) 방식 구현
    	
    	// 정답 변수
    	int answer = 0;
    	
    	// i는 2번째부터 N번째까지 탐색
    	// 예시 1의 경우, 3부터 7, 8, 6, 2, 9, 4까지 탐색을 의미
    	for(int i=2; i<=N; i++){
    		// 최대값을 담는 변수
    		int max = 0;
    		
    		// i번째 배열의 왼쪽 탐색
    		for(int j=i-1; j>=1; j--){
    			// 탐색조건 1)i번째 배열의 값이 j번째 배열보다 큰수인 경우
    			if(arr[j]<arr[i]){
    				// 탐색조건 2)j번째 부분증가수열의 최대길이가 현재의 최대값 보다 큰 경우,
    				if(max < dp[j]){
    					max = dp[j];
    				}
    			}
    			// i번째 부분증가수열의 최대값은,
    			// i번째보다 왼쪽에 있는 arr 배열의 값 중에서,
    			// arr배열의 숫자값이 arr[i]보다 작고,
    			// 부분증가수열의 최대값(dp배열값)이 가장 큰 경우보다 +1이다.
    			dp[i] = max + 1;
    			// 현재까지 부분증가수열의 최대값 중, 가장 길이가 긴 값을 answer에 넣는다.
    			answer = Math.max(answer, dp[i]);
    		}
    		
    	}
    	
    	return answer;
    } // end of solution

} // end of Main