Height Checker — 기대 순서와 다른 위치 세기

기대 순서와 다른 위치를 세기, 어떤 문제인가요?

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

학생들이 키가 작거나 같은 순서, 즉 감소하지 않는 순서로 서 있어야 합니다. 현재 키 순서 heights가 주어질 때, 올바른 순서 expected와 비교해서 값이 다른 인덱스의 개수를 반환하세요.

예시는 이렇습니다.

• heights = [1,1,4,2,1,3] → 3
  • 기대 순서: [1,1,1,2,3,4]
  • 다른 위치: 인덱스 2, 4, 5
• heights = [5,1,2,3,4] → 5
  • 기대 순서: [1,2,3,4,5]
  • 모든 위치가 다름
• heights = [1,2,3,4,5] → 0
  • 이미 기대 순서와 같음

제약은 다음과 같습니다.

• 1 <= heights.length <= 100
• 1 <= heights[i] <= 100

이 문제의 핵심은 학생을 실제로 이동시키는 횟수를 구하는 것이 아닙니다. 현재 배열과 정렬된 배열을 같은 인덱스끼리 비교해서 다른 위치가 몇 개인지 세는 문제입니다. 이 글에서는 배열을 복사해서 정렬하는 풀이부터, 키 범위가 작다는 조건을 이용한 카운팅 정렬 풀이까지 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

문제를 비교 문제로 보기

현재 순서가 있습니다.

heights = [1, 1, 4, 2, 1, 3]

올바른 순서는 이 배열을 정렬한 결과입니다.

expected = [1, 1, 1, 2, 3, 4]

이제 같은 인덱스끼리 비교하면 됩니다.

index:     0  1  2  3  4  5
heights:   1  1  4  2  1  3
expected:  1  1  1  2  3  4
              같 같 다 같 다 다

다른 위치는 3개입니다.

즉 문제는 다음처럼 바꿔 볼 수 있습니다.

정렬된 배열을 만들고
원래 배열과 다른 인덱스 수를 세라

Phase 1. 복사한 배열을 정렬해서 비교하기

가장 직관적인 방법은 heights를 복사한 뒤 정렬하는 것입니다.

fun heightChecker(heights: IntArray): Int {
    val expected = heights.copyOf()
    expected.sort()

    var count = 0

    for (i in heights.indices) {
        if (heights[i] != expected[i]) {
            count++
        }
    }

    return count
}

흐름은 단순합니다.

1. heights를 expected로 복사
2. expected를 오름차순 정렬
3. 같은 인덱스끼리 비교
4. 값이 다르면 count++

heights = [1,1,4,2,1,3]이라면:

expected = [1,1,1,2,3,4]

비교 결과 인덱스 2, 4, 5가 다르므로 3을 반환합니다.

시간 복잡도는 정렬 때문에 O(n log n)이고, 복사 배열 때문에 추가 공간은 O(n)입니다.

제약이 작기 때문에 이 풀이만으로도 충분히 통과합니다.

Phase 2. 키 개수를 세고 기대 배열 만들기

이 문제는 키 범위가 작습니다.

1 <= heights[i] <= 100

따라서 정렬 대신 각 키가 몇 번 나오는지 세는 방식, 즉 카운팅 정렬을 사용할 수 있습니다.

fun heightChecker(heights: IntArray): Int {
    val counts = IntArray(101)

    for (height in heights) {
        counts[height]++
    }

    val expected = IntArray(heights.size)
    var index = 0

    for (height in 1..100) {
        repeat(counts[height]) {
            expected[index] = height
            index++
        }
    }

    var count = 0

    for (i in heights.indices) {
        if (heights[i] != expected[i]) {
            count++
        }
    }

    return count
}

예를 들어 heights = [1,1,4,2,1,3]이면 개수는 다음과 같습니다.

1 -> 3개
2 -> 1개
3 -> 1개
4 -> 1개

이 정보를 작은 키부터 펼치면 기대 배열이 됩니다.

[1, 1, 1, 2, 3, 4]

시간 복잡도는 O(n + k)입니다. 여기서 k는 가능한 키 범위인 100입니다. 문제 제약에서는 사실상 O(n)으로 볼 수 있습니다.

추가 공간은 counts와 expected 때문에 O(n + k)입니다.

Phase 3. 기대 배열 없이 바로 비교하기

카운팅 정렬을 조금 더 줄이면, expected 배열을 따로 만들지 않고 바로 비교할 수 있습니다.

fun heightChecker(heights: IntArray): Int {
    val counts = IntArray(101)

    for (height in heights) {
        counts[height]++
    }

    var expectedHeight = 1
    var count = 0

    for (i in heights.indices) {
        while (counts[expectedHeight] == 0) {
            expectedHeight++
        }

        if (heights[i] != expectedHeight) {
            count++
        }

        counts[expectedHeight]--
    }

    return count
}

여기서 expectedHeight는 현재 인덱스에 와야 하는 키입니다.

counts는 정렬된 배열을 직접 만들지 않아도, 다음 기대 값을 알려 줍니다.

counts[1] = 3
counts[2] = 1
counts[3] = 1
counts[4] = 1

처음 세 칸의 기대 키는 1, 그 다음은 2, 그 다음은 3, 마지막은 4입니다.

각 인덱스에서:

1. 아직 남아 있는 가장 작은 키를 찾음
2. 현재 heights[i]와 비교
3. 기대 키 하나를 사용했으므로 counts[expectedHeight]--

이렇게 하면 기대 배열을 만들지 않고도 다른 위치 개수를 셀 수 있습니다.

시간 복잡도는 O(n + k)이고, 추가 공간은 counts 배열 하나라서 O(k)입니다. 여기서 k = 100이므로 문제 제약에서는 상수 공간처럼 볼 수 있습니다.

왜 이동 횟수를 세지 않나요?

이 문제는 "몇 명을 움직여야 하는가"를 묻는 문제가 아닙니다.

묻는 것은 정확히 이것입니다.

heights[i] != expected[i] 인 i의 개수

예를 들어:

heights  = [5, 1, 2, 3, 4]
expected = [1, 2, 3, 4, 5]

실제로 학생을 어떤 방식으로 이동시킬지는 중요하지 않습니다. 문제는 모든 인덱스가 기대 값과 다르므로 5를 반환합니다.

그래서 정렬된 배열과 현재 배열을 비교하는 관점이 가장 직접적입니다.

엣지 케이스

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

입력	결과	이유
[1]	0	원소 하나는 이미 정렬 상태
[1,1,4,2,1,3]	3	인덱스 2, 4, 5가 다름
[5,1,2,3,4]	5	모든 위치가 기대 순서와 다름
[1,2,3,4,5]	0	이미 정렬되어 있음
[2,1,2,1,1,2]	3	정렬 후 앞쪽 1들과 비교
[100,100,100]	0	같은 키만 있으면 이미 정렬 상태

특히 이미 정렬된 배열과 모든 위치가 다른 배열을 모두 확인해야 합니다. 이 문제는 정렬 여부만 묻는 것이 아니라, 다른 위치의 개수를 반환하기 때문입니다.

세 풀이를 다시 비교

풀이	시간	공간	특징
복사 후 정렬해서 비교	O(n log n)	O(n)	가장 직관적
카운팅 정렬로 기대 배열 생성	O(n + k)	O(n + k)	키 범위가 작다는 조건 활용
카운팅 배열로 바로 비교	O(n + k)	O(k)	기대 배열 없이 mismatch만 계산

마무리

1. 이 문제는 이동 횟수가 아니라 기대 순서와 다른 인덱스 개수를 세는 문제입니다 — 정렬된 배열과 비교하면 됩니다
2. 가장 직관적인 풀이는 배열을 복사해 정렬한 뒤 비교하는 방식입니다 — O(n log n)으로 충분히 통과합니다
3. 키 범위가 1..100으로 작기 때문에 카운팅 정렬을 사용할 수 있습니다 — 정렬 비용을 O(n + k)로 줄일 수 있습니다
4. 기대 배열을 만들지 않고도 counts로 다음 기대 키를 알 수 있습니다 — 공간을 O(k)로 줄입니다
5. 최종적으로는 같은 인덱스에서 값이 다른지만 세면 됩니다 — 문제의 반환값은 mismatch count입니다