파이썬으로 정렬된 리스트에서 고유한 숫자 개수 구하기

문제 개요

정렬된 숫자 리스트 nums가 주어졌을 때, 이 리스트에 포함된 고유한(중복되지 않은) 요소의 개수를 구하는 것이 목표입니다.

예를 들어 입력이 다음과 같다면,

nums = [3, 3, 3, 4, 5, 7, 7]

고유한 숫자는 [3, 4, 5, 7] 네 가지이므로 출력은 4가 됩니다.

풀이 접근 방법

파이썬의 집합(Set) 자료구조를 활용하면 간단하게 해결할 수 있습니다. 집합은 중복 값을 허용하지 않기 때문에, 요소를 하나씩 확인하며 처음 등장하는 값만 카운트하면 됩니다.

알고리즘 단계

1. 새로운 빈 집합 s를 생성합니다.
2. 카운터 변수 cnt를 0으로 초기화합니다.
3. nums의 각 요소 i에 대해 반복합니다.
4. i가 s에 존재하지 않으면 i를 s에 추가하고 cnt를 1 증가시킵니다.
5. 반복이 끝나면 cnt를 반환합니다.

구현 예제

class Solution:
    def solve(self, nums):
        s = set()
        cnt = 0
        for i in nums:
            if i not in s:
                s.add(i)
                cnt += 1
        return cnt

ob = Solution()
print(ob.solve([3, 3, 3, 4, 5, 7, 7]))

입력

[3, 3, 3, 4, 5, 7, 7]

출력

4

더 간결한 대안: len(set()) 활용

위 과정은 파이썬에서 한 줄로 처리할 수도 있습니다. 리스트를 집합으로 변환하면 중복이 자동으로 제거되므로, 그 길이를 구하면 곧 고유한 요소의 개수가 됩니다.

def solve(nums):
    return len(set(nums))

print(solve([3, 3, 3, 4, 5, 7, 7]))  # 출력: 4

정렬된 리스트에 최적화된 방법

리스트가 이미 정렬되어 있다는 조건을 활용하면 추가 메모리 없이도 해결할 수 있습니다. 인접한 두 요소를 비교하여 값이 달라질 때마다 카운트를 증가시키는 방식으로, 이 경우 공간 복잡도를 O(1)까지 줄일 수 있습니다.

def solve_sorted(nums):
    if not nums:
        return 0
    cnt = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[i - 1]:
            cnt += 1
    return cnt

복잡도 분석

• 집합 기반 방법: 시간 복잡도 O(n), 공간 복잡도 O(n)
• 인접 요소 비교 방법(정렬된 리스트 전용): 시간 복잡도 O(n), 공간 복잡도 O(1)