Valid Mountain Array — 올라갔다가 내려오는 배열 판별하기

배열이 산 모양인지 확인하기, 어떤 문제인가요?

LeetCode 941번 문제는 이렇게 주어집니다.

정수 배열 arr가 주어집니다. 이 배열이 유효한 산 배열이면 true, 아니면 false를 반환하세요.

산 배열이 되려면 다음 조건을 만족해야 합니다.

• 길이가 최소 3이어야 함
• 중간 어딘가에 꼭대기 peak가 있어야 함
• 꼭대기 전까지는 엄격하게 증가해야 함
• 꼭대기 이후에는 엄격하게 감소해야 함
• 꼭대기는 첫 번째나 마지막 원소가 될 수 없음

예시는 이렇습니다.

• arr = [2,1] → false
  • 길이가 3보다 작음
• arr = [3,5,5] → false
  • 같은 값 5,5가 이어지므로 엄격한 증가·감소가 아님
• arr = [0,3,2,1] → true
  • 0 -> 3으로 올라간 뒤 3 -> 2 -> 1로 내려감

제약은 다음과 같습니다.

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^4

이 문제의 핵심은 단순히 최댓값이 있는지 확인하는 것이 아닙니다. 최댓값까지는 계속 올라가야 하고, 그 이후에는 계속 내려가야 합니다. 또한 같은 값이 붙어 있으면 산 배열이 아닙니다. 이 글에서는 꼭대기를 찾고 양쪽을 검사하는 풀이부터, 한 번 순회로 올라가는 구간과 내려가는 구간을 확인하는 풀이까지 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

산 배열의 조건을 다시 보기

산 배열은 다음 모양이어야 합니다.

arr[0] < arr[1] < ... < arr[peak]
arr[peak] > arr[peak + 1] > ... > arr[last]

중요한 조건은 세 가지입니다.

• 올라가는 구간이 적어도 하나 있어야 함
• 내려가는 구간이 적어도 하나 있어야 함
• 인접한 값이 같으면 안 됨

예를 들어:

[1, 2, 3]      -> 내려가는 구간이 없음
[3, 2, 1]      -> 올라가는 구간이 없음
[1, 2, 2, 1]   -> 같은 값이 있어 엄격한 산이 아님
[1, 3, 2]      -> 유효한 산 배열

즉 꼭대기는 반드시 배열의 중간에 있어야 합니다.

Phase 1. 최댓값 위치를 찾고 양쪽 검사하기

가장 직관적인 방법은 먼저 최댓값의 위치를 찾고, 그 왼쪽과 오른쪽이 조건을 만족하는지 확인하는 것입니다.

fun validMountainArray(arr: IntArray): Boolean {
    if (arr.size < 3) return false

    var peak = 0

    for (i in arr.indices) {
        if (arr[i] > arr[peak]) {
            peak = i
        }
    }

    if (peak == 0 || peak == arr.lastIndex) {
        return false
    }

    for (i in 0 until peak) {
        if (arr[i] >= arr[i + 1]) {
            return false
        }
    }

    for (i in peak until arr.lastIndex) {
        if (arr[i] <= arr[i + 1]) {
            return false
        }
    }

    return true
}

흐름은 이렇습니다.

1. 배열 길이가 3보다 작으면 바로 false
2. 최댓값 위치 peak를 찾음
3. peak가 첫 번째나 마지막이면 false
4. 왼쪽 구간이 모두 증가하는지 확인
5. 오른쪽 구간이 모두 감소하는지 확인

arr = [0,3,2,1]이라면 peak = 1입니다.

왼쪽: 0 < 3
오른쪽: 3 > 2 > 1

둘 다 만족하므로 true입니다.

반면 arr = [3,5,5]에서는 peak = 1이지만 오른쪽 검사에서:

5 <= 5

가 되어 false가 됩니다.

이 풀이는 시간 복잡도 O(n), 추가 공간 O(1)입니다. 다만 최댓값을 찾고 다시 양쪽을 검사하므로 배열을 여러 번 지나갑니다.

Phase 2. 올라갈 수 있을 때까지 올라가고, 내려갈 수 있을 때까지 내려가기

더 자연스러운 풀이는 실제 산을 타듯이 인덱스를 움직이는 것입니다.

fun validMountainArray(arr: IntArray): Boolean {
    val n = arr.size
    var i = 0

    while (i + 1 < n && arr[i] < arr[i + 1]) {
        i++
    }

    if (i == 0 || i == n - 1) {
        return false
    }

    while (i + 1 < n && arr[i] > arr[i + 1]) {
        i++
    }

    return i == n - 1
}

첫 번째 while은 증가하는 동안 계속 이동합니다.

[0, 3, 2, 1]
 0 -> 3 까지 이동
 i는 값 3의 위치

이때 i가 꼭대기 후보입니다.

그런데 다음 두 경우는 산 배열이 아닙니다.

i == 0       -> 처음부터 내려감, 올라가는 구간 없음
i == n - 1   -> 끝까지 올라감, 내려가는 구간 없음

그래서 중간 꼭대기인지 확인합니다.

그 다음 두 번째 while로 감소하는 동안 계속 이동합니다. 마지막 인덱스까지 도착했다면 전체 배열이 산 모양입니다.

arr = [0, 3, 2, 1]

증가: 0 -> 3
감소: 3 -> 2 -> 1
마지막까지 도착 -> true

반대로 arr = [0,3,2,2,1]이라면:

증가: 0 -> 3
감소: 3 -> 2
2 == 2 에서 멈춤
마지막까지 못 감 -> false

같은 값은 증가도 감소도 아니므로 자연스럽게 걸러집니다.

시간 복잡도는 O(n)이고, 추가 공간은 O(1)입니다.

Phase 3. 양쪽에서 꼭대기를 향해 이동하기

양쪽에서 출발하는 방식도 가능합니다.

fun validMountainArray(arr: IntArray): Boolean {
    val n = arr.size
    var left = 0
    var right = n - 1

    while (left + 1 < n && arr[left] < arr[left + 1]) {
        left++
    }

    while (right - 1 >= 0 && arr[right - 1] > arr[right]) {
        right--
    }

    return left == right && left != 0 && right != n - 1
}

의미는 이렇습니다.

• left: 왼쪽에서 증가하면서 도착한 위치
• right: 오른쪽에서 감소 관계를 거꾸로 따라가며 도착한 위치

유효한 산 배열이라면 두 포인터는 같은 꼭대기에서 만나야 합니다.

arr = [0, 3, 2, 1]

left  -> 3에서 멈춤
right -> 3에서 멈춤
같은 위치이고 양 끝이 아님 -> true

반대로 같은 값이 있거나, 증가 구간만 있거나, 감소 구간만 있으면 두 포인터가 올바른 중간 꼭대기에서 만나지 못합니다.

이 풀이도 시간 복잡도 O(n), 추가 공간 O(1)입니다. 다만 실제 구현에서는 Phase 2처럼 한 포인터로 올라갔다가 내려가는 코드가 더 읽기 쉽습니다.

엣지 케이스

자주 확인해 볼 만한 입력은 이렇습니다.

입력	결과	이유
[2,1]	false	길이가 3보다 작음
[3,5,5]	false	같은 값이 붙어 있음
[0,3,2,1]	true	증가 후 감소
[1,2,3]	false	내려가는 구간 없음
[3,2,1]	false	올라가는 구간 없음
[1,3,2]	true	가장 짧은 산 배열
[1,2,1,2]	false	내려간 뒤 다시 올라감

특히 arr = [1,2,3]과 arr = [3,2,1]은 꼭 확인해야 합니다. 둘 다 한쪽 방향으로는 잘 움직이지만, 산 배열은 반드시 올라가는 구간과 내려가는 구간을 모두 가져야 합니다.

세 풀이를 다시 비교

풀이	시간	공간	특징
최댓값 찾고 양쪽 검사	O(n)	O(1)	조건을 분리해서 이해하기 쉬움
한 포인터로 상승 후 하강	O(n)	O(1)	가장 간결한 기본 풀이
양쪽 포인터로 꼭대기 찾기	O(n)	O(1)	양쪽 구간이 같은 꼭대기에서 만나는지 확인

마무리

1. 산 배열은 길이가 최소 3이어야 합니다 — 올라가는 구간과 내려가는 구간이 모두 필요합니다
2. 꼭대기는 첫 번째나 마지막 원소가 될 수 없습니다 — 한쪽 구간만 있으면 산이 아닙니다
3. 증가와 감소는 모두 엄격해야 합니다 — 같은 값이 붙어 있으면 false입니다
4. 한 포인터로 올라갈 수 있을 때까지 올라간 뒤 내려갈 수 있을 때까지 내려가면 됩니다 — 마지막까지 도착하면 유효한 산 배열입니다
5. 최종 풀이는 O(n) 시간, O(1) 공간입니다 — 배열을 한 번 훑는 방식으로 충분합니다