Coding Interview

[코딩 인터뷰][LeetCode] – Increasing Triplet Subsequence

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

문제 정보

문제 출처 : https://leetcode.com/problems/increasing-triplet-subsequence/
카테고리 : DP(?), Greedy(?)
난이도 : 쉬움


문제 설명

어떤 정수 리스트 A가 주어졌을 때, i < j < k이고, A[i] < A[j] < A[k]인 (i, j, k)가 존재하는지를 리턴하여라


문제 풀이

Simple – O(N)의 방법

배열 Min, Max를 정의한다.
Min[i]는 인덱스 A[0] ~ A[i]의 수 중에서 가장 작은 값을 저장한다.
Max[i]는 A[i] ~ A[size – 1] 중에서 가장 큰 값을 저장한다.
A[i]에 대해 A[i]와 Min[i]를 비교해서 A[i] > Min[i]이면, i 이전에 A[i] > A[j]인 j가 있다는 말이다.
같은 원리로 A[i]와 Max[j]를 비교해서 A[i] < Max[i]이면, i 이후에 A[i] < A[j]인 j가 있다는 말이다.
따라서 모든 i에 대해 Min[i] < A[i] < Max[i]인 i가 존재하면 True를 리턴하고, 아니면 False를 리턴하면 된다.


코드
class Solution(object):
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        
        # Return False on minimum size exception
        if len(nums) < 3:
            return False
        
        # Init Size
        size = len(nums)
        Min, Max = [0] * size, [0] * size
        
        # Init Min, Max array
        Min[0] = nums[0]
        for i in range(1, size):
            Min[i] = min(nums[i], Min[i - 1])
        Max[size - 1] = nums[size - 1]
        for i in reversed(range(len(nums) - 1)):
            Max[i] = max(nums[i], Max[i + 1])
        
        # Compare nums[i] with min before i and max after i
        for i in range(1, size - 1):
            if Min[i] < nums[i] and nums[i] < Max[i]:
                return True
        return False

코딩 인터뷰 – Increasing Triplet Subsequence

admin

Recent Posts

2024년 11월 17일 일요일 – 서울 생활 129주차

괌여행 아내와 함께 괌으로 여행을 갔다. 출산 이후로 둘만 가는 첫 여행이다. 하와이가 일본인들이 많이…

3일 ago

2024년 11월 3일 일요일 – 서울 생활 127주차

반복적인 일상 매일 아침 일어나 회사에 출근하고, 저녁을 먹고 돌아오는 일상의 반복이다. 주말은 가족을 보러…

3주 ago

2024년 10월 6일 일요일 – 서울 생활 123주차

Planning A well-structured plan has the following characteristics:   First, the ultimate vision you aim to…

2개월 ago

2024년 9월 29일 일요일 – 서울 생활 122주차

English The most common problem for English learners like myself is that we often use…

2개월 ago

2024년 9월 22일 일요일 – 서울 생활 121주차

추석 추석을 맞아 친가 외가 처가 어르신들을 모두 뵙고 돌아왔다. 아이가 태어난지는 좀 됐지만 한국에서…

2개월 ago

2024년 9월 8일 일요일 – 서울 생활 119주차

주말 이번주는 아내가 올라와서 주말을 함께 보냈다. 둘만 밥도 먹고 뮤지컬도 보고, 모임도 나가고 집에서…

2개월 ago

This website uses cookies.