[leetcode][334] Increasing Triplet Subsequence

문제 : https://leetcode.com/problems/increasing-triplet-subsequence/

---

nums 배열이 주어진다.

인덱스 i, j, k (0 <= i < j < k <= n-1)라 할 때, nums[i] < nums[j] < nums[k] 를 충족하는 부분배열이 존재하는지 구하는 문제이다.

 

nums = [1,0,2,-1,3] 를 예로 들어 보자.

3개 수만 오름차순이 되면 되므로 첫번째, 두번째 숫자만 저장하고 nums 배열을 탐색하면서 탐색하는 수를 3번째 수라 가정하고 정답이 가능한지 판단한다.

첫번째 원소를 첫번째 수(one), int형의 가장 큰 수를 두번째 수(two)라 가정하고 배열을 2번째 원소부터(1번째 원소는 첫번째 수라 가정했으므로) 탐색한다. let) 탐색하고 있는 수 = three

오름차순을 구해야 하므로 저장되는 변수(one, two)에는 최대한 작은 수일 수록 좋다.

 

그러나 greedy 방식으로 무조건 작은 수만 저장하는 경우 예시 배열의 답은 구할 수 없다.

[1,0,2,-1,3]

가장 작은 수들만 저장한다면 위와 같이 정답이 가능하지만 정답이 없다고 결론짓는다.

[1,0,2,-1,3]

정답은 위와 같은 경우 가능하다.

for three in nums[1:]:
  if three > two: #1
    return True
  if three > one: #2
    two = three
  if three < one: #3
    one = three

#1 탐색 중인 수(three)가 two보다 큰 경우, one < two < three 인 부분배열이 있다는 뜻이므로 정답이 가능하다.

식은 (one<two<three)라 하였지만 정답이라 판단할 당시 

#2 탐색 중인 수(three)가 one보다 큰 경우, 즉. one < three < two 인 경우, 두번째 수를 탐색중인 수로 갱신한다. 

두 번째 수를 갱신하는 이유는 사전에 말했듯이 최대한 작은 수를 저장할수록 오름차순을 만들기 쉽기 때문이다.

#3 탐색 중인 수(three)가 one보다 작은 경우, 즉. three < one < two 인 경우, 첫번째 수를 탐색중인 수로 갱신한다.

이 때, 두 번째 수는 갱신하지 않는게 가장 중요하다.

-1을 탐색 중이라 할 때, [one, two] 는 [0, 2]일 것이다.

-1은 0보다 작기 때문에 [-1, 2]로 갱신되고 3 탐색 시, two(2) 보다 3이 크기 때문에 정답이 가능하다고 판단한다.

만약, [-1, INT_MAX]로 갱신하는 경우 [-1, 3]으로 배열을 갱신하기 때문에 정답인지 제대로 판단할 수 없다.

 

시간복잡도는 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/334.%20Increasing%20Triplet%20Subsequence.py