문제 소개
N개의 숫자로 이루어진 배열이 주어졌을 때, b[i] < b[j] < b[k]를 만족하면서 인덱스 순서가 i < j < k인 세 원소를 선형 시간, 즉 O(n) 복잡도 안에 찾아야 합니다. 조건을 만족하는 삼중 항이 여러 개라면 그중 하나만 출력하면 됩니다.
예를 들어 입력 배열이 [13, 12, 11, 6, 7, 3, 31]이라면, 결과는 [6, 7, 31]이 됩니다.
접근 방법
이 문제는 단순한 세 겹 반복문으로 풀면 O(n³)이 걸리지만, 보조 배열 두 개를 활용하면 한 번의 순회로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- smaller[i]: 인덱스 i의 왼쪽에 있으면서 A[i]보다 작은 원소의 인덱스를 저장합니다. 없다면 -1을 저장합니다.
- greater[i]: 인덱스 i의 오른쪽에 있으면서 A[i]보다 큰 원소의 인덱스를 저장합니다. 없다면 -1을 저장합니다.
배열을 한 번은 왼쪽에서 오른쪽으로, 또 한 번은 오른쪽에서 왼쪽으로 순회하면서 위 두 배열을 채운 뒤, smaller[i]와 greater[i]가 모두 -1이 아닌 인덱스 i를 찾으면 그 지점이 곧 증가하는 삼중 항의 가운데 원소가 됩니다.
알고리즘 단계
- n := 배열 A의 크기로 설정
- maximum := n-1, minimum := 0으로 초기화
- smaller 배열을 생성하고 smaller[0] := -1로 설정한 뒤, 왼쪽부터 순회하며 현재까지의 최솟값 인덱스를 기록
- greater 배열을 생성하고 greater[n-1] := -1로 설정한 뒤, 오른쪽부터 순회하며 현재까지의 최댓값 인덱스를 기록
- smaller[i] != -1이고 greater[i] != -1인 i를 발견하면 A[smaller[i]], A[i], A[greater[i]]를 반환
- 끝까지 찾지 못하면 "Nothing" 반환
구현 예제
아래 코드를 통해 실제 동작 방식을 확인해 보겠습니다.
def find_inc_seq(A):
n = len(A)
maximum = n - 1
minimum = 0
# 왼쪽에서 더 작은 원소의 인덱스 저장
smaller = [0] * n
smaller[0] = -1
for i in range(1, n):
if A[i] <= A[minimum]:
minimum = i
smaller[i] = -1
else:
smaller[i] = minimum
# 오른쪽에서 더 큰 원소의 인덱스 저장
greater = [0] * n
greater[n - 1] = -1
for i in range(n - 2, -1, -1):
if A[i] >= A[maximum]:
maximum = i
greater[i] = -1
else:
greater[i] = maximum
# 세 번째 순회로 정답 탐색
for i in range(0, n):
if smaller[i] != -1 and greater[i] != -1:
return A[smaller[i]], A[i], A[greater[i]]
return "Nothing"
arr = [13, 12, 11, 6, 7, 3, 31]
print(find_inc_seq(arr))실행 결과
입력
[13, 12, 11, 6, 7, 3, 31]
출력
(6, 7, 31)
복잡도 분석
이 알고리즘은 배열을 총 세 번 순회하지만, 각 순회가 모두 독립적인 선형 스캔이므로 전체 시간 복잡도는 O(n)입니다. 추가로 사용되는 smaller와 greater 배열 때문에 공간 복잡도 역시 O(n)입니다. 원본 코드에서 고정 크기 10000의 배열을 사용했지만, 입력 배열과 동일한 크기 n으로 할당하면 메모리를 더 효율적으로 사용할 수 있습니다.