문제 개요
학생들이 사진 촬영을 위해 키를 기준으로 비내림차순(오름차순)으로 줄을 서야 한다고 가정해 보겠습니다. 학생들의 키가 담긴 배열이 주어졌을 때, 올바른 위치에 서 있지 않은 학생의 최소 수를 구하는 것이 이번 문제의 목표입니다.
예를 들어 배열이 [1, 1, 4, 2, 1, 3]이라면 정답은 3입니다. 이 배열을 정렬하면 [1, 1, 1, 2, 3, 4]가 되는데, 키가 4인 학생과 마지막 두 자리의 학생들이 올바른 위치에 서 있지 않기 때문입니다.
풀이 접근 방법
이 문제는 정렬 기반의 간단한 비교만으로 해결할 수 있습니다. 핵심 아이디어는 '올바르게 정렬된 상태'와 '현재 상태'를 한 요소씩 비교하여, 서로 다른 지점의 개수를 세는 것입니다. 구체적인 단계는 다음과 같습니다.
- answer := 0 으로 초기화합니다.
- x := 원본 배열을 정렬한 새로운 배열로 설정합니다.
- y := 원본 배열로 설정합니다.
- i를 0부터 배열 크기 - 1까지 반복합니다.
- x[i]와 y[i]가 같지 않으면 answer를 1 증가시킵니다.
- 최종적으로 answer를 반환합니다.
Python 코드 예시
아래 구현을 통해 더 쉽게 이해할 수 있습니다.
class Solution(object):
def heightChecker(self, heights):
ans = 0
x = sorted(heights)
y = heights
for i in range(len(x)):
if x[i] != y[i]:
ans += 1
return ans
ob1 = Solution()
print(ob1.heightChecker([1, 2, 4, 2, 1, 3]))위 코드에서 sorted(heights)는 원본 배열을 변경하지 않고 정렬된 새 리스트를 반환하므로, 원본 배열 y와 안전하게 비교할 수 있다는 점에 유의하세요.
입력
[1, 2, 4, 2, 1, 3]
출력
4
입력 배열 [1, 2, 4, 2, 1, 3]을 정렬하면 [1, 1, 2, 2, 3, 4]가 됩니다. 인덱스 1, 2, 4, 5의 네 곳에서 값이 서로 다르므로 결과는 4입니다.
복잡도 분석
배열을 정렬하는 데 O(n log n)의 시간이 소요되고, 요소 비교에는 O(n)이 걸리므로 전체 시간 복잡도는 O(n log n)입니다. 또한 정렬된 복사본을 저장해야 하므로 공간 복잡도는 O(n)입니다.