정수로 이루어진 배열 A가 주어졌을 때, 이 배열이 유효한 산(mountain) 배열인지 확인하는 문제를 살펴보겠습니다.
산 배열의 정의
배열 A가 산 배열이 되려면 다음 조건들을 모두 만족해야 합니다.
- 배열 A의 크기는 3 이상이어야 합니다.
- 배열 내에 특정 인덱스 i가 존재하여 다음 두 조건을 충족해야 합니다.
- A[0] < A[1] < ... < A[i-1] < A[i] — 꼭대기까지 값이 계속 증가합니다.
- A[i] > A[i+1] > ... > A[A.length - 1] — 꼭대기 이후 값이 계속 감소합니다.
즉, 배열이 먼저 오르고(증가 구간) 반드시 한 번 내려야(감소 구간) 하며, 평평한 구간이 있어서는 안 됩니다.
예를 들어 입력이 [0,3,2,1]이라면, 0에서 3까지 증가한 뒤 2, 1로 감소하므로 출력은 True입니다.
해결 방법
다음 단계에 따라 문제를 해결할 수 있습니다.
- 배열 A의 크기가 3보다 작으면 False를 반환합니다.
- i := 1로 초기화합니다.
- i가 배열 길이보다 작고 A[i] > A[i-1]인 동안 i를 1씩 증가시켜 증가 구간을 지나갑니다.
- 이 시점에서 i가 1이거나 i가 배열 길이와 같으면 False를 반환합니다. (i가 1이면 증가 구간이 없다는 뜻이고, i가 끝에 도달했다면 감소 구간이 없다는 의미입니다.)
- i가 배열 길이보다 작고 A[i] < A[i-1]인 동안 i를 1씩 증가시켜 감소 구간을 지나갑니다.
- 마지막으로 i가 배열 길이와 같으면 True, 그렇지 않으면 False를 반환합니다.
구현 예제
class Solution: def validMountainArray(self, A): if(len(A)<3): return False i = 1 while(i<len(A) and A[i]>A[i-1]): i+=1 if(i==1 or i==len(A)): return False while(i<len(A) and A[i]<A[i-1]): i+=1 return i==len(A) ob = Solution() print(ob.validMountainArray([0,3,2,1]))
입력
[0,3,2,1]
출력
True
복잡도 분석
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가적인 저장 공간 없이 인덱스 변수 하나만 사용하므로 공간 복잡도는 O(1)입니다.