(코딩테스트) 백준_11053_가장 긴 증가하는 부분 수열 / DP

 

 

 

최초 제시한 답 (정답)     * 시간 복잡도 = O(N²)

package codingTest;

import java.util.*;
import java.io.*;


public class Backjun_11053_tets {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N=Integer.parseInt(br.readLine());
		StringTokenizer st =new StringTokenizer(br.readLine()); 
		int[] list = new int[N];
		int[] dp = new int[N];
		for(int i =0;i<N;i++) {
			list[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i =0;i<N;i++) {
			dp[i] = 1; //기본 1값 다 세팅
		}
		
		
		/*
		 * 6 
		 * 
		 * 10 20 10 30 20 50
		 */
		
		// dp 다 채움
		for(int i=1;i<N;i++) {
			for(int k=0;k<i;k++) {
				if(list[k] < list[i]) {										
					dp[i] = Math.max(dp[i], dp[k]+1);					
				}				
			}			
		}
		int max =0;
		for(int i =0;i<N;i++) {
			max = Math.max(max, dp[i]);
		}
		System.out.print(max);
		
		
	}

}

 

 

 

 

 

 

최적화된 답 (정답)   * 시간 복잡도  =   O(N log N)          DP 풀이는 아님.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        List<Integer> lis = new ArrayList<>();

        for (int num : arr) {
            int idx = Collections.binarySearch(lis, num);
            if (idx < 0) {
                idx = -(idx + 1);  // 삽입할 위치
            }
            if (idx == lis.size()) {
                lis.add(num);     // 새로운 값 추가
            } else {
                lis.set(idx, num); // 더 작은 값으로 교체
            }
        }

        System.out.println(lis.size());  // LIS 길이
    }
}

 

느낀점

 이중 for 로 시간복잡도 N2를 사용하지 않고  

컬렉션 arraylist에 차례로 값을 담아 마지막에 list 길이로 결과 값 출력한다는게 인상 깊었다.

 

 

처음 어려웠던점. 

1. binarySearch + set으로 기존 값 교체 

- binarySearch는 list 안에  정수 값이 들어가야할 위치를 리턴 시켜주는데 

키 값이 존재하면 양수로 위치 index

키 값이 존재하지 않는다면 음수로 위치 index-1 값 해준다  (그래서 양수 전환시 ( - index)+1 이 필요하다. )

그 후 if문에서 인덱스의 길이와 list의 길이를 비교하여 뒤에 들어올 값이면 add로 뒤에 저장 

만약 중간에 값 교체라면 set으로 값 교체 (처음 이 부분이 이해가 안갔다. 기존 값을 버리고? 신규 값 교체??? 삭제될 값이 크면 굳이 버릴 필요가 없지 않나라고 생각했으나 문제에서는 수열이라 순서를 지켜야하기에 뒤에 올 값이 크든말든 set 될 값이 더 작다면 다음 들어올 값의 허용되는 부분이 더 늘어나기에 작은 값으로 교체 해주는게 확률적으로 더 이득이라 기존의 큰 값은 삭제가 맞다.....  )