Algorithm - Increasing Triplet Subsequence(Greedy)

다용도리모콘·2021년 8월 28일
0

CodingTest

목록 보기
33/34

문제

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

코드

function increasingTriplet(nums: number[]): boolean {

    var maxValue, midValue = nums[0];
    for (var i = 1; i < nums.length; i++) {
        if (nums[i] <= midValue) {
            midValue = nums[i];
        } else if ((nums[i] <= maxValue) || maxValue == undefined) {
            maxValue = nums[i];
        } else {
            return true;
        }

    }
    return false;
};

풀이

최고, 중간, 최소 값을 찾는 것을 목표로 반복을 진행한다. 최소값과 중간값을 가능한 한 작은 값으로 줄여가면서 이 두 값보다 큰 값을 찾으면 세 값을 모두 찾게 되므로 true를 리턴한다.

회고

세 값이 붙어있어야 한다는 조건이 없었기 때문에 처음에는 완성될 가능성이 있는 경우의 수를 다 저장하면서 진행 해야하나라는 생각을 했었는데

0개의 댓글