문제 개요
정렬되지 않은 배열이 하나 주어졌을 때, 이 배열 안에 길이가 3인 증가 부분 수열이 존재하는지 확인해야 합니다.
형식적으로 표현하면 다음과 같습니다.
- 배열에 인덱스 i, j, k가 존재하여
- 0 ≤ i < j < k ≤ n-1 조건을 만족하면서 arr[i] < arr[j] < arr[k]를 만족하면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
해결 접근 방법
이 문제는 그리디(Greedy) 기법을 활용하면 선형 시간에 해결할 수 있습니다. 핵심 아이디어는 배열을 한 번 순회하면서 '가장 작은 값(small)'과 '두 번째로 작은 값(big)'이라는 두 개의 후보 값을 계속 유지하는 것입니다.
- small := 무한대, big := 무한대로 초기화
- 배열의 각 원소 i에 대해:
- i <= small이면 small := i로 갱신
- 그렇지 않고 i <= big이면 big := i로 갱신
- 둘 다 아니라면 true 반환
- 순회가 끝날 때까지 true가 반환되지 않으면 false 반환
여기서 중요한 포인트는 small과 big이 서로 다른 위치의 값일 필요가 없다는 것입니다. big이 갱신된 적이 있다는 사실 자체가 'big보다 작은 값이 반드시 앞에 존재했다'는 것을 보장하기 때문에, 나중에 big보다 큰 원소를 만나는 순간 곧바로 정답임을 확신할 수 있습니다.
예제 코드
class Solution(object): def increasingTriplet(self, nums): small,big = 100000000000000000000,100000000000000000000 for i in nums: if i <= small: small = i elif i<=big: big = i else : return True return False ob1 = Solution() print(ob1.increasingTriplet([5,3,8,2,7,9,4]))
입력
[5,3,8,2,7,9,4]
출력
True
동작 과정 살펴보기
입력 배열 [5, 3, 8, 2, 7, 9, 4]가 알고리즘에 의해 처리되는 과정은 다음과 같습니다.
- 5 → small 갱신 (small = 5)
- 3 → small 갱신 (small = 3)
- 8 → big 갱신 (big = 8)
- 2 → small 갱신 (small = 2)
- 7 → big 갱신 (big = 7)
- 9 → 9가 small(2)과 big(7)보다 모두 크므로 true 반환
실제로 2 < 7 < 9 또는 3 < 8 < 9처럼 길이 3의 증가 부분 수열이 존재하므로 결과는 True가 됩니다.
복잡도 분석
시간 복잡도: O(n) — 배열을 딱 한 번만 순회합니다.
공간 복잡도: O(1) — small과 big 두 변수만 추가로 사용합니다.