[Algorithm] 증가하는 부분 수열 leetcode Increasing Triplet Subsequence

leetcode - Increasing Triplet Subsequence

문제 링크: leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/781/

Account Login - LeetCode

 

이 문제는 증가하는 부분 수열의 길이의 최댓값을 구하는 문제로 풀었다.

이 최댓값이 3보다 크거나 같으면 True, 작으면 False

 

O(n)으로 풀 수 있다는데 그건 모르겠고

O(n^2)으로 푼 방법을 적어보고자 한다.

 

자기 자신이 마지막인, 증가하는 부분 수열의 길이를 동적 계획법으로 찾는 방법을 적용했다.

처음 주어지는 배열을 nums, 증가하는 부분 수열의 길이를 담은 배열을 result라고 하겠다. result는 모두 1로 초기화한다.

 

0 - n 까지 for문을 돈다. 이 변수를 i라고 하겠다.

이 안에 0 - i-1 까지 for문을 한번 더 돈다.

자기 자신보다 작은 수가 나오면, 그 수가 마지막인 부분 수열에 자기 자신을 더하는 것이므로 result 값에 1을 더한다.

코드는 다음과 같다.

res = False
        n = len(nums)
        result = [1] * n 

        for i in range(n):
            for j in range(i):
                if(nums[i]>nums[j]):
                    result[i] = result[j] + 1
        increasing = max(result)
        print(result)
        if(increasing >= 3):
            res = True
        return res

그러나 이렇게 하면 문제가 생긴다. 예를 들어

 

nums:  20,100,10,12,5,13

result: 1, 2, 1, 2, 1, 2

 

가 된다. 13은 3의 값을 가져야 한다.

왜 이런 문제가 발생하냐면, 가장 마지막에 만난 자신보다 작은 수의 5의 값에 1을 더하기 때문이다. 이래서 처음에 틀렸다.

 

따라서 result값은 자기보다 작은 수 중 가장 긴 증가하는 부분 수열을 가지고 있는 수의 result 값으로 유지되어야 한다.

그래서 고친 코드는 다음과 같다. 이러면 통과한다.

 

res = False
        n = len(nums)
        result = [1] * n 

        for i in range(n):
            for j in range(i):
                if(nums[i]>nums[j]):
                    result[i] = max(result[i], result[j] + 1)
        increasing = max(result)
        print(result)
        if(increasing >= 3):
            res = True
        return res