[BOJ] 백준 [11722] 가장 긴 감소하는 부분수열 JAVA

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

11722번: 가장 긴 감소하는 부분 수열

문제

풀이

LIS(LDS) 풀이는 3가지다.

1. 완전탐색으로 푸는경우 => 시간복잡도 O(n^3)

2. DP => O(N^2)

3. 이진탐색 => O(nlongn)

 

완전탐색인 경우 for문을 이용한 단순 반복이므로 생략

 

DP로 접근 할 경우 , 부분 중복 되는부분을 찾아 최적화 시켜야한다.

2중 for문( 바깥쪽 i , 안쪽 j ) 로 주어진 수열 arr 를 탐색하면 ( 0 <= j < i )

dp[i] = max ( dp[i], dp[j]+1 )  가 된다.

즉, i가 점점 전진할때 이전에 기록해 놓은 값들을 활용하여 완전 탐색 했을때의 반복 하나를 줄일수 있음.

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 = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] dp = new int[N];
        Arrays.fill(dp,1);
        for(int i=0;i<N;i++)
            for(int j=0;j<i;j++)
                if(arr[i] < arr[j] )
                    dp[i] = Math.max(dp[i],dp[j]+1);               
        Arrays.stream(dp).max().ifPresent(System.out::println);
 
    }
}
 

 

이진탐색으로 접근 할 경우 , 결과가 담길 배열 result 에 기존 배열 arr 를 순차적으로 탐색하면서 적절한 위치에 배치하는 방식으로 해결한다.

배열을 역순으로 뒤집어서 lis 방식을 적용하면 감소하는 부분수열이 되므로 , 처음에 배열을 뒤집고 시작

 

결과 배열에 들어가는 경우가 두 가지가 있다.

 

1.주여진 배열을 탐색할때 뒤의 값이 더 높으면 그냥 추가 ( size 라는 인덱스는 맨 앞에서 부터 출발 )

if(result[size-1] < arr[i])
result[size++] = arr[i];

 

2. 뒤의 값이 더 작은 경우엔 적절한 위치를 binarySearch 함수를 통해서 반환 받은값을 인덱스로 사용하여 추가

   int index = Arrays.binarySearch(result, 0, size, arr[i]);
   if(index < 0)
       index = -index-1;
   result[index] = arr[i];

 

 

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];
        String[] input = br.readLine().split(" ");
        for(int i=N-1;i>=0;i--)
            arr[(N-1)-i] = Integer.parseInt(input[i]);
        int[] result = new int[N];
        int size = 0;
        result[size++] = arr[0];
        for(int i=1;i<N;i++){
            if(result[size-1] < arr[i])
                result[size++] = arr[i];
            else{
                int index = Arrays.binarySearch(result, 0, size, arr[i]);
                if(index < 0)
                    index = -index-1;
                result[index] = arr[i];
            }
        }
        System.out.println(size);
    }
}
 

 

시간차이가 확실히 난다.