Python으로 리스트를 정렬했을 때 제자리에 있는 요소 개수 구하기

숫자로 이루어진 리스트 nums가 주어졌을 때, 이 리스트를 정렬했을 경우 원래 자리 그대로 유지되는 요소가 몇 개인지 구하는 문제입니다.

예를 들어 입력이 [2, 8, 4, 5, 11]이라면 결과는 2가 됩니다. 정렬된 리스트는 [2, 4, 5, 8, 11]이며, 이때 2와 11만 원래 위치와 동일하게 유지되기 때문입니다.

해결 접근 방법

이 문제는 다음과 같은 단계로 해결할 수 있습니다.

• 리스트 nums를 정렬한 결과를 s에 저장합니다.
• 카운터 변수 count를 0으로 초기화합니다.
• 인덱스 0부터 리스트 길이까지 반복하면서 s[i]와 nums[i]가 같은지 비교하고, 같다면 count를 1 증가시킵니다.
• 반복이 끝나면 count를 반환합니다.

핵심 아이디어는 간단합니다. 정렬 전과 정렬 후의 값을 같은 인덱스끼리 비교하면, 해당 값이 이미 올바른 위치에 있는지 바로 판별할 수 있습니다.

구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

class Solution:
    def solve(self, nums):
        s = sorted(nums)
        count = 0
        for i in range(len(nums)):
            if s[i] == nums[i]:
                count += 1
        return count
ob = Solution()
print(ob.solve([2, 8, 4, 5, 11]))

입력

[2, 8, 4, 5, 11]

출력

2

복잡도 분석

정렬 과정이 포함되므로 시간 복잡도는 O(n log n)이고, 정렬된 복사본을 저장해야 하므로 공간 복잡도는 O(n)입니다.

한 줄 표현으로 더 간결하게

파이썬의 zip()과 sum()을 활용하면 위 로직을 한 줄로 작성할 수도 있습니다.

def solve(nums):
    return sum(a == b for a, b in zip(nums, sorted(nums)))

두 방식 모두 동일한 결과를 반환하지만, 반복문을 직접 사용하는 첫 번째 방법이 로직을 이해하기에는 더 직관적입니다.