[코딩 인터뷰][HackerRank] The Longest Increasing Subsequence

※ 이 포스트는 HackerRank 문제인 The Longest Increasing Subsequence 해설을 담고 있습니다.
본 풀이는 Optimal하지 않을 수 있으며, HackerRank에서의 Submission 통과만을 보장합니다.

문제 정보

문제 출처 : The Longest Increasing Subsequence (https://www.hackerrank.com/challenges/longest-increasing-subsequent/problem)
카테고리 : DP / Stack, Binary Search
난이도 : 보통 ~ 중급

문제 설명

정수 배열이 주어진다. 임의로 원소를 고른 것들이 증가수열이 되도록 할 때, 가능한 최대의 길이를 출력하여라.
예를 들어 1 5 4 2 3 7의 경우 1 2 3 7을 골라서 길이 4인 증가수열을 만들 수 있다.

문제 풀이

DP – O(N^2)

동적계획법으로 해결하는 법이 가장 보편적으로 알려진 방법이다. D[i]는 i를 마지막 원소로 하는 증가수열의 최대 길이이다.
Arr[0]에서 Arr[i – 1]까지를 탐색하면서 Arr[i]보다 작은 Arr[j]을 가지는 j들의 D[j] 중 가장 큰 것에 + 1을 하면 된다.
만약 Arr[i]보다 작은 Arr[j]가 존재하지 않는다면, D[i] = 1이 된다. i보다 작은 j들에 대해서 D[j]는 Arr[j]를 포함하는 증가수열의 최대 길이이기 때문에, 그 중 가장 긴 수열 뒤에 Arr[i]를 추가한다고 생각하면 이해하기 쉽다.

Binary Search – O(N log N)

배열 List는 List[i]에 길이가 (i + 1)인 증가수열의 맨 마지막 원소를 저장한다. 증가수열 [1, 3, 5, 6]이 있다면 List[3] = 6인 것이다.
List의 원소는 가능한 작은 값으로 유지해야할 것이므로, 자연스럽게 List의 원소들은 오름차순으로 정렬된다.
즉, 길이 i + 1인 증가수열에서 길이 i인 증가수열을 만들 수 있으므로, 이 조건은 위배되지 않는다.

Arr의 왼쪽부터 오른쪽으로 탐색하면서, List에 원소 Arr[i]를 추가하려고 하는 상황을 살펴보자.
List에 대해 이분 검색을 수행해서 Arr[i]보다 작은 것들 중에서 가장 큰 원소의 인덱스를 찾는다.
그 idx가 List의 마지막 원소라고 생각해보자. 이 말은 기존의 가장 긴 증가수열에 대해 Arr[i]를 마지막에 추가하는 것과 같다.
그 이외의 경우엔 List[idx + 1]을 Arr[i]로 대체한다. 이것은 List[idx]를 마지막으로 하는 증가수열에 Arr[i]를 새로 추가한 것이다.
그런데, 이 새로운 수열은 List[idx + 1]이 똑같은 길이를 갖는다. Arr[i] <= List[idx + 1]이므로 List의 원소를 가능한 작게 만들기 위해선 List[idx + 1]에 Arr[i]를 덮어씌워야한다.

즉, 요약하자면 다음과 같다.
1. 각 Arr[i]에 대해서
2. List의 Arr[i]보다 작은 원소들 중 가장 큰 값의 인덱스를 얻는다.
3-1. 이 idx가 List의 마지막 값이라면, Arr[i]를 새롭게 List에 추가.
3-2. 이외의 경우 List[idx + 1] = Arr[i]

이 방식은 증가수열 자체를 저장하지는 않는다.
즉, List의 원소들을 나열한 것은 그 값만 오름차순이지 그 값들의 Arr안에서의 인덱스까지 오름차순이라고 볼 수 없다는 말이다.
List는 List[i]를 마지막 원소로 하는 길이 i + 1의 증가수열이 존재한다는 사실만을 저장할 수 있다.

더 자세한 설명은 GeeksforGeeks의 설명을 참조.

코드

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the longestIncreasingSubsequence function below.
def getIdx(List, n):
    l, r = 0, len(List) - 1
    ret = -1
    while l <= r:
        mid = (l + r) // 2
        if List[mid] < n:
            ret = mid
            l = mid + 1
        else:
            r = mid - 1
    return ret

def longestIncreasingSubsequence(arr):
    N = len(arr)
    List = []
    for i in range(N):
        idx = getIdx(List, arr[i])
        if idx == len(List) - 1:
            List.append(arr[i])
        else:
            List[idx + 1] = arr[i]
    return len(List)


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    arr = []

    for _ in range(n):
        arr_item = int(input())
        arr.append(arr_item)

    result = longestIncreasingSubsequence(arr)

    fptr.write(str(result) + '\n')

    fptr.close()

코딩 인터뷰 – The Longest Increasing Subsequence