백준 11053: 가장 긴 증가하는 부분 수열 11053: 가장 긴 증가하는 부분 수열 [Silver 2]

 

백준 11053 : 가장 긴 증가하는 부분 수열

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

 

 

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

 

 

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

 

 

내 답

 

1. 수열(arr) 배열, 길이를 저장할 배열(tmp) 각각 선언

 

2. LIS 계산

   수열을 첫번째 배열부터 돌면서, 이전의 값들과 비교하며 LIS를 업데이트

   현재 값이 이전값과 같으면, 같은 순서로 저장.

   다를 경우 이전 항들을 순회하며 현재 값보다 작은 수 중 가장 높은 순서의 다음 순서를 저장한다.

import java.util.Arrays;
import java.util.Scanner;

public class S2_가장긴증가하는부분수열 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] arr = new int[N];
        int[] tmp = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.fill(tmp, 1);
        int max = 1;

        for (int i = 1; i < N; i++) {
            // 같은 값이면 이전 값과 같은 LIS 길이 유지
            if (arr[i] == arr[i - 1]) {
                tmp[i] = tmp[i - 1];
            } else {
                // 이전 값들을 탐색하여 LIS 갱신
                for (int j = 0; j < i; j++) {
                    if (arr[j] >= arr[i]) {
                        continue;
                    } else {
                        // 현재 값보다 작은 값들 중 최대 LIS 길이를 갱신
                        if (tmp[i] <= tmp[j]) {
                            tmp[i] = tmp[j] + 1;
                        }
                    }
                }
            }
            // 최대 LIS 길이 갱신
            max = Math.max(max, tmp[i]);
        }

        System.out.println(max);
    }
}

 

 

모법 답

 1. 이분 탐색을 활용하여 시간복잡도 O(N^2)에서 O(NlogN)으로 줄일 수 있다.

 

2. 리스트를 사용해 증가 부분 수열을 저장

 

3. 이분탐색으로 리스트에 삽입할 위치를 찾음

 

import java.util.ArrayList;
import java.util.Scanner;

public class LIS_이분탐색 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        ArrayList<Integer> lis = new ArrayList<>(); // LIS를 저장할 리스트

        for (int num : arr) {
            // num이 LIS의 마지막 값보다 클 경우, LIS에 추가
            if (lis.isEmpty() || lis.get(lis.size() - 1) < num) {
                lis.add(num);
            } else {
                // num이 들어갈 위치를 이분 탐색으로 찾음
                int idx = binarySearch(lis, num);
                lis.set(idx, num); // LIS 갱신
            }
        }

        // LIS 리스트의 길이가 최종 결과
        System.out.println(lis.size());
    }

    // 이분 탐색을 통해 LIS에 들어갈 자리 찾기
    private static int binarySearch(ArrayList<Integer> lis, int num) {
        int left = 0;
        int right = lis.size() - 1;

        while (left < right) {
            int mid = (left + right) / 2;
            if (lis.get(mid) < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}