알고리즘 풀이 - 백준 12015(가장 긴 증가하는 부분 수열 2, 그리디(Greedy))

 

관련글

 

관련글

 

그리디 알고리즘 관련 포스팅은 여기를 참조
가장 긴 증가하는 부분 수열(LIS) 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

가장 긴 증가하는 부분 수열의 길이를 구하는 문제

 

 

2. 풀이

 

이 문제는 가장 긴 증가하는 부분 수열(LIS) 관련 포스팅을 참고하면 됩니다.

관련 포스팅은 여기를 참조

 

해당 포스팅에 모든 내용을 정리하였습니다.

다만, 이 문제의 경우, N의 크기가 백만으로 크기 때문에 단순 2중 반복문으로 해결 시, 시간 초과가 발생합니다.

 

따라서 위 포스팅의 가장 마지막 부분을 참고하여 O(nlogn)으로 해결할 수 있는 방법으로 풀어야 합니다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

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

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());
        String[] s = br.readLine().split(" ");
        
        int[] a = new int[n];
        int[] v = new int[n];
        Arrays.fill(v, Integer.MAX_VALUE);
        
        int idx = -1;
        for(int i=0; i < n; i++){
            a[i] = Integer.parseInt(s[i]);
            
            // 가장 처음의 위치이거나 가장 최근에 삽입된 값보다 현재 기존 배열의 위치의 값이 큰 경우
            if(idx == -1 || v[idx] < a[i]){
                // 현재 위치의 다음에 해당 값을 삽입
                v[++idx] = a[i];
            } else {
                // 이진 탐색을 통해 삽입할 위치를 찾는다.
                int j = binarySearch(v, a[i]);
                v[j] = a[i];
            }
        }
        System.out.println(idx+1);
        br.close();
    }
    
    // 이진 탐색을 수행하는 메소드
    private static int binarySearch(int[] v, int num){
        int start = 0;
        int end = v.length-1;
        
        while(start <= end){
            int mid = (start + end) / 2;
            if(v[mid] < num){
                start = mid+1;
            } else if(v[mid] > num){
                end = mid;
            } else {
                return mid;
            }
        }
        return start;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.