[백준] 30. 가장 긴 증가하는 부분 수열 2 12015 해설

가장 긴 증가하는 부분 수열 2

12015번: 가장 긴 증가하는 부분 수열 2

갈수록 풀지 못하는 문제가 많아지고 있습니다.

해당 문제도 마찬가지로 풀지 못하였는데 풀이 방법이 전혀 생각지도 못한 방법이면서 너무나 간단하여 스스로 정리할 겸 글을 쓰게 되었습니다.

문제

 

풀이

이전에 풀었던 가장 긴 증가하는 부분 수열 1의 경우 dp를 통해 시간 복잡도 O(n^2)으로 문제를 해결할 수 있었습니다.

하지만 2의 경우 N의 범위가 1,000,000이기 때문에 다른 방법을 사용해 줘야 됩니다.

 

정답은 이진 탐색을 활용하는 것이었습니다.

N번의 탐색을 돌면서 매번 이진탐색을 해줘도 시간 복잡도는 O(n log n)이기 때문에 시간제한에 걸리지 않습니다.

 

풀이 방법은 간단합니다. (풀이 방법은 간단하지만 풀이 방법을 생각해 내기는 어렵습니다.)

너무 간단해서 이해하고 나면 당연한 사실처럼 느껴지기에 이를 구체적으로 설명하는 것보다 예시를 통해 설명하겠습니다.

 

수열이 10, 20, 10, 3, 5, 30, 20, 50 이 주어졌을 때 상황입니다.

예시

 

1번째 수열 10의 경우

임시 배열이 비어있기 때문에 바로 추가해 줍니다.

1

 

2번째 수열 20의 경우

임시 배열의 마지막 index인 10보다 크기 때문에 바로 추가해 줍니다.

2

 

3번째 수열 10의 경우

임시 배열의 마지막 index인 20보다 작기 때문에 임시 배열 안에서 이분 탐색을 통해 10의 위치를 찾아줍니다.

이분 탐색을 통해 10의 위치를 찾았지만 이미 10이 존재하기 때문에 넘어가 줍니다.

3

 

4번째 수열 3의 경우 

임시 배열의 마지막 index인 20보다 작기 때문에 임시 배열 안에서 이분 탐색을 통해 3의 위치를 찾아줍니다.

찾은 위치에 값을 3으로 교체해 줍니다.

4

 

5번째 수열 5의 경우

임시 배열의 마지막 index인 20보다 작기 때문에 임시 배열 안에서 이분 탐색을 통해 5의 위치를 찾아줍니다.

찾은 위치에 값을 5로 교체해 줍니다.

5

 

6번째 수열 30의 경우

임시 배열의 마지막 index인 5보다 크기 때문에 바로 추가해 줍니다.

6

 

7번째 수열 20의 경우

임시 배열의 마지막 index인 30보다 작기 때문에 임시 배열 안에서 이분 탐색을 통해 20의 위치를 찾아줍니다.

찾은 위치에 값을 20으로 교체해 줍니다.

7

 

마지막 수열 50의 경우

임시 배열의 마지막 index인 20보다 크기 때문에 바로 추가해 줍니다.

마지막

 

 

결과적으로 임시 배열 안에 있는 요소의 개수가 가장 긴 증가하는 부분 수열의 길이라는 것을 알 수 있습니다.

결국 우리는 수열의 길이만 알면 되기 때문에 임시 배열의 마지막 값보다 큰 수가 오면 추가해 주고 작은 수가 오면 기존 값에 덮어 씌어 주면 됩니다.

 

의사 코드로 보면 다음과 같습니다.

for (num in 수열) {
    
    if (임시 배열이 비어있는 경우) {
    	임시 배열에 추가
        continue
    }

    if (임시 배열 마지막 값 < num) {
        임시 배열에 추가
    } else {
   	이진탐색(num)
    }
}

 

아래는 전체 코드입니다.

import java.io.StreamTokenizer

/**
 * LIS(Longest Increasing subsequence)의 이분탐색 풀이
 */
fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }

    var N = input()
    val arr = IntArray(N)  // 임시 배열
    var cur = -1 // 임시 배열 현재 위치

    while(N-- > 0) {
        val num = input()

        // 임시 배열이 비어있는 경우
        if (cur == -1) {
            arr[++cur] = num
            continue
        }

        // 임시 배열의 마지막 값과 비교
        if (arr[cur] < num) {
            arr[++cur] = num
        } else {
            binarySearch(0, cur, num, arr)
        }
    }
    print(cur+1)

}

fun binarySearch(start: Int, end: Int, num: Int, arr: IntArray) {
    var s = start
    var e = end
    while (s <= e) {
        val mid = (s+e)/2
        if (num == arr[mid]) {
            return
        } else if (num < arr[mid]) {
            e = mid-1
        } else {
            s = mid+1
        }
    }
    // 덮어 씌어서 갱신
    arr[s] = num
}