문제 개요
숫자로 이루어진 리스트 A가 주어졌을 때, 리스트 안의 모든 중복 숫자를 찾아낸 뒤 각 숫자의 마지막으로 등장한 항목만 제거하는 프로그램을 만들어 보겠습니다.
예를 들어 입력이 [10, 30, 40, 10, 30, 50]이라면, 10과 30이 각각 두 번씩 등장합니다. 따라서 마지막에 등장한 10과 30을 제거한 결과인 [10, 30, 40, 50]이 출력됩니다.
해결 접근 방식
핵심 아이디어는 딕셔너리(맵) 두 개를 활용하는 것입니다.
d: 각 숫자가 리스트 전체에서 몇 번 등장하는지 저장하는 맵seen: 왼쪽부터 순회하면서 지금까지 몇 번 마주쳤는지 기록하는 맵
전체 진행 단계는 다음과 같습니다.
- 첫 번째 순회에서 각 숫자의 총 등장 횟수를
d에 기록합니다. - 두 번째 순회에서 현재 원소의 총 횟수
n을 확인하고,seen에 지금까지 본 횟수를 누적합니다. - 현재까지 본 횟수가 총 횟수와 같고(
n == seen[nums[i]]) 그 값이 1보다 크다면, 해당 원소가 이 숫자의 마지막 등장이므로 리스트에서 삭제합니다. - 삭제하면 뒤의 요소들이 한 칸씩 앞으로 당겨지므로 인덱스
i를 1 감소시켜 다음 원소를 건너뛰지 않도록 합니다. - 모든 순회가 끝나면 수정된 리스트를 반환합니다.
구현 코드
class Solution:
def solve(self, nums):
seen = {}
d = {}
# 1단계: 각 숫자의 총 등장 횟수 계산
for i in range(len(nums)):
if nums[i] not in d:
d[nums[i]] = 1
else:
d[nums[i]] += 1
# 2단계: 마지막 등장 항목 제거
i = 0
while i < len(nums):
n = d[nums[i]]
if nums[i] not in seen:
seen[nums[i]] = 1
else:
seen[nums[i]] += 1
# 마지막 등장이면서 중복인 경우 삭제
if n == seen[nums[i]] and n > 1:
nums.pop(i)
i -= 1
i += 1
return nums
ob = Solution()
print(ob.solve([10, 30, 40, 10, 30, 50]))입력
[10, 30, 40, 10, 30, 50]
출력
[10, 30, 40, 50]
동작 원리 상세 설명
입력 [10, 30, 40, 10, 30, 50]을 기준으로 코드의 흐름을 살펴보겠습니다.
- 첫 번째 순회가 끝나면
d는{10: 2, 30: 2, 40: 1, 50: 1}이 됩니다. - 인덱스 3에 있는
10에 도달하면seen[10]이 2가 되어 총 횟수 2와 일치하고, 1보다 크므로 삭제 대상이 됩니다. - 삭제 후 한 칸 당겨진 자리에 온
30역시 마지막 등장이므로 같은 방식으로 제거됩니다. 40과50은 한 번만 등장했기 때문에(n == 1) 조건을 만족하지 않아 그대로 유지됩니다.
복잡도 분석
- 시간 복잡도: 리스트를 두 번 순회하므로 탐색 자체는 O(n)입니다. 다만
pop()호출 시 요소 이동 비용이 발생하므로, 중복이 매우 많은 최악의 경우 O(n²)까지 늘어날 수 있습니다. - 공간 복잡도: O(k) — 여기서 k는 서로 다른 숫자의 개수입니다.