LeetCode 334. Increasing Triplet Subsequence [Java]

https://leetcode.com/problems/increasing-triplet-subsequence/description/

시나리오

• a와b를 Integer.MAX_VALUE로 초기화한다.
• 배열을 순회하며 현재 요소가 a보다 작거나 같으면 현재 요소를 a에 갱신. 현재 요소가 a보다는 크나 b보다는 작거나 같으면 b 갱신. a와 b 둘보다 크면 배열 내 triplet subsequence가 존재한다는 것이므로 return true;
• 순회 완료 전까지 return 되지 않으면 return false해준다.

코드

class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums.length < 3) {
            return false;
        }

        int a = Integer.MAX_VALUE;
        int b = Integer.MAX_VALUE;

        for(int i=0; i<nums.length; i++){
            if(nums[i]<=a){
                a = nums[i];
                continue;
            }
            if(nums[i]<=b){
                b = nums[i];
                continue;
            }
            return true;
        }

        return false;
    }
}

헷갈렸던 부분

nums = [20, 100, 10, 12, 5 ,13]라는 케이스가 있을 때, a=10, b=12 -> a=5, b=12로 갱신되고 13이 현재 요소가 됨에 따라 true를 return하게 된다. 그런데 이것은 12, 5, 13 순으로 triplet subsequence가 발생하는 것을 의미하게 돼서 결국엔 틀린 답이 되지 않는가?

-> 그렇지 않다. a에 5가 들어갈 수 있다는 것은 5가 나오기 이전, a에는 5<=a<12의 값이 들어 있었다는 것을 의미한다. 따라서 a가 5로 갱신된다 한들 12보다 작은값이 들어있었다는 사실은 변하지 않기 때문에 12보다 큰값이 그 이후에 나오게 되면 true를 return하면 된다.

즉, a에 b보다 작은 값이 들어가려면 b가 나오기 이전 b보다 작은 값이 나와야만 가능하다.