Replace Elements with Greatest Element on Right Side — 오른쪽 최댓값으로 바꾸기

오른쪽에서 가장 큰 값으로 바꾸기, 어떤 문제인가요?

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

정수 배열 arr가 주어집니다. 각 원소를 그 원소의 오른쪽에 있는 값 중 가장 큰 값으로 바꾸세요. 마지막 원소의 오른쪽에는 아무 값도 없으므로 -1로 바꿉니다.

예시는 이렇습니다.

• arr = [17,18,5,4,6,1] → [18,6,6,6,1,-1]
• arr = [400] → [-1]

첫 번째 예시를 인덱스별로 보면:

17의 오른쪽 최댓값 -> 18
18의 오른쪽 최댓값 -> 6
5의 오른쪽 최댓값  -> 6
4의 오른쪽 최댓값  -> 6
6의 오른쪽 최댓값  -> 1
1의 오른쪽 값 없음 -> -1

제약은 다음과 같습니다.

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

이 문제의 핵심은 각 위치마다 "오른쪽 전체의 최댓값"이 필요하다는 점입니다. 왼쪽에서 오른쪽으로 보면 매번 뒤쪽을 다시 확인해야 하지만, 오른쪽에서 왼쪽으로 보면 지금까지 본 값 중 최댓값만 유지하면 됩니다. 이 글에서는 완전 탐색 풀이부터, suffix 최댓값 배열 풀이, 그리고 제자리 역방향 순회 풀이까지 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

문제를 오른쪽 구간의 최댓값으로 보기

각 인덱스 i에 필요한 값은 다음입니다.

max(arr[i + 1], arr[i + 2], ..., arr[last])

마지막 인덱스는 오른쪽 구간이 없으므로 -1입니다.

예를 들어:

arr = [17, 18, 5, 4, 6, 1]

이면 각 위치에 필요한 값은:

i=0 -> max(18, 5, 4, 6, 1) = 18
i=1 -> max(5, 4, 6, 1) = 6
i=2 -> max(4, 6, 1) = 6
i=3 -> max(6, 1) = 6
i=4 -> max(1) = 1
i=5 -> 오른쪽 없음 = -1

입니다.

Phase 1. 각 위치마다 오른쪽을 다시 훑기

가장 직접적인 방법은 각 인덱스마다 오른쪽 원소를 모두 확인하는 것입니다.

fun replaceElements(arr: IntArray): IntArray {
    val result = IntArray(arr.size)

    for (i in arr.indices) {
        var maxRight = -1

        for (j in i + 1 until arr.size) {
            maxRight = maxOf(maxRight, arr[j])
        }

        result[i] = maxRight
    }

    return result
}

이 방식은 문제 정의를 그대로 코드로 옮긴 풀이입니다.

• i를 하나 정함
• i + 1부터 끝까지 보며 최댓값을 찾음
• 그 값을 결과 배열에 저장

정답은 맞지만, 원소가 n개일 때 오른쪽 구간을 계속 다시 훑습니다. 시간 복잡도는 O(n^2)이고, 결과 배열 때문에 추가 공간도 O(n)입니다.

Phase 2. 오른쪽 최댓값 배열 만들기

반복 계산을 줄이려면 각 위치의 오른쪽 최댓값을 미리 저장할 수 있습니다.

fun replaceElements(arr: IntArray): IntArray {
    val n = arr.size
    val suffixMax = IntArray(n)

    suffixMax[n - 1] = -1

    for (i in n - 2 downTo 0) {
        suffixMax[i] = maxOf(suffixMax[i + 1], arr[i + 1])
    }

    return suffixMax
}

suffixMax[i]는 i 오른쪽에 있는 값 중 최댓값입니다.

arr       = [17, 18, 5, 4, 6, 1]
suffixMax = [18,  6, 6, 6, 1,-1]

핵심 관계는 다음과 같습니다.

suffixMax[i] = max(suffixMax[i + 1], arr[i + 1])

i의 오른쪽 최댓값은:

• 바로 오른쪽 값 arr[i + 1]
• 그보다 더 오른쪽의 최댓값 suffixMax[i + 1]

중 더 큰 값입니다.

이 방식은 시간 복잡도 O(n)입니다. 하지만 suffixMax 배열을 따로 만들기 때문에 추가 공간은 O(n)입니다.

Phase 3. 오른쪽에서 왼쪽으로 제자리 갱신하기

최종 풀이는 별도 배열 없이 arr 자체를 바꿉니다.

오른쪽에서 왼쪽으로 이동하면서, 지금까지 오른쪽에서 본 값 중 최댓값을 maxRight에 저장합니다.

fun replaceElements(arr: IntArray): IntArray {
    var maxRight = -1

    for (i in arr.lastIndex downTo 0) {
        val current = arr[i]
        arr[i] = maxRight
        maxRight = maxOf(maxRight, current)
    }

    return arr
}

arr = [17,18,5,4,6,1]를 따라가 봅시다.

처음 maxRight = -1

i=5, current=1
arr[5] = -1
maxRight = max(-1, 1) = 1

i=4, current=6
arr[4] = 1
maxRight = max(1, 6) = 6

i=3, current=4
arr[3] = 6
maxRight = max(6, 4) = 6

i=2, current=5
arr[2] = 6
maxRight = max(6, 5) = 6

i=1, current=18
arr[1] = 6
maxRight = max(6, 18) = 18

i=0, current=17
arr[0] = 18
maxRight = max(18, 17) = 18

결과는 다음과 같습니다.

[18, 6, 6, 6, 1, -1]

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

왜 current를 먼저 저장해야 하나요?

최종 풀이에서 이 순서가 중요합니다.

val current = arr[i]
arr[i] = maxRight
maxRight = maxOf(maxRight, current)

arr[i]를 먼저 maxRight로 덮어쓰면 원래 값이 사라집니다. 그런데 원래 arr[i]는 왼쪽 원소들에게는 "오른쪽에 있는 값"입니다.

예를 들어 arr = [17,18,5,4,6,1]에서 18은 17의 오른쪽 최댓값이 될 수 있습니다. 그래서 18 위치를 6으로 바꾸기 전에 원래 값 18을 current에 보관해야 합니다.

즉 순서는 다음과 같습니다.

1. 현재 원래 값을 저장
2. 현재 칸을 오른쪽 최댓값으로 교체
3. 원래 값을 이용해 maxRight 갱신

이 순서가 제자리 풀이의 핵심입니다.

왜 초기값이 -1인가요?

마지막 원소의 오른쪽에는 아무 값도 없습니다. 문제에서 마지막 원소는 -1로 바꾸라고 했으므로, 오른쪽에서 시작할 때의 최댓값을 -1로 두면 자연스럽게 처리됩니다.

maxRight = -1
마지막 칸 = maxRight

또한 제약상 arr[i] >= 1이므로 실제 배열 값과 -1이 헷갈릴 일도 없습니다.

엣지 케이스

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

입력	결과	이유
[400]	[-1]	오른쪽 원소가 없음
[17,18,5,4,6,1]	[18,6,6,6,1,-1]	기본 예시
[1,2,3,4]	[4,4,4,-1]	오른쪽 최댓값이 계속 마지막 값
[4,3,2,1]	[3,2,1,-1]	바로 오른쪽 값이 항상 최댓값
[5,5,5]	[5,5,-1]	같은 값도 최댓값으로 사용 가능

특히 길이가 1인 배열을 확인해야 합니다. 반복문은 한 번만 실행되고, 해당 원소는 바로 -1로 바뀝니다.

세 풀이를 다시 비교

풀이	시간	공간	특징
각 위치마다 오른쪽 전체 탐색	O(n^2)	O(n)	문제 정의를 그대로 구현
suffix 최댓값 배열 사용	O(n)	O(n)	오른쪽 최댓값을 미리 저장
오른쪽에서 왼쪽으로 제자리 갱신	O(n)	O(1)	가장 효율적인 기본 풀이

마무리

1. 각 원소는 자기 오른쪽 구간의 최댓값으로 바뀝니다 — 마지막 원소는 항상 -1입니다
2. 왼쪽에서 오른쪽으로 보면 오른쪽 구간을 계속 다시 확인하게 됩니다 — 완전 탐색은 O(n^2)입니다
3. 오른쪽에서 왼쪽으로 보면 지금까지 본 최댓값 하나만 유지하면 됩니다 — maxRight가 그 역할을 합니다
4. 현재 값을 덮어쓰기 전에 current에 저장해야 합니다 — 왼쪽 원소들의 최댓값 후보로 계속 필요하기 때문입니다
5. 최종 풀이는 O(n) 시간, O(1) 공간입니다 — 배열을 한 번 역방향으로 순회하면서 제자리에서 해결합니다