문제 개요
숫자로 구성된 연결 리스트가 주어졌을 때, 여러 번 등장하는 숫자들을 제거하고 각 숫자는 한 번만 남기는 프로그램을 만들어야 합니다. 이때 중요한 조건은 원본 연결 리스트에서의 등장 순서를 그대로 유지해야 한다는 점입니다.
예를 들어, 입력이 [2 -> 4 -> 6 -> 1 -> 4 -> 6 -> 9]라면, 4와 6이 중복되므로 출력은 [2 -> 4 -> 6 -> 1 -> 9]가 됩니다.
해결 방법
이 문제는 집합(Set) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 집합은 특정 값이 이미 존재하는지 O(1) 시간에 확인할 수 있기 때문입니다. 알고리즘의 동작 단계는 다음과 같습니다.
- 노드가 null이 아닌 경우:
- 새로운 빈 집합(set) l을 생성합니다.
- temp를 현재 노드로 지정합니다.
- temp의 값을 집합 l에 삽입합니다.
- temp의 다음 노드가 존재하는 동안 반복합니다.
- 다음 노드의 값이 집합 l에 없다면: 해당 값을 l에 추가하고 temp를 다음 노드로 이동합니다.
- 다음 노드의 값이 이미 l에 있다면: 중복이므로 해당 노드를 연결 리스트에서 제거합니다(temp.next를 건너뛰도록 재연결).
- 마지막으로 head 노드인 node를 반환합니다.
예제 코드
아래 파이썬 구현 예제를 통해 더 잘 이해할 수 있습니다.
class ListNode:
def __init__(self, data, next = None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def print_list(head):
ptr = head
print('[', end = "")
while ptr:
print(ptr.val, end = ", ")
ptr = ptr.next
print(']')
class Solution:
def solve(self, node):
if node:
l = set()
temp = node
l.add(temp.val)
while temp.next:
if temp.next.val not in l:
l.add(temp.next.val)
temp = temp.next
else:
temp.next = temp.next.next
return node
ob = Solution()
head = make_list([2, 4, 6, 1, 4, 6, 9])
print_list(ob.solve(head))입력
[2, 4, 6, 1, 4, 6, 9]
출력
[2, 4, 6, 1, 9]
시간 복잡도 분석
이 알고리즘은 연결 리스트의 모든 노드를 한 번씩만 순회하며, 집합에서의 값 검색 및 삽입은 평균적으로 O(1)이므로 전체 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 중복 없는 값을 저장하기 위한 집합 때문에 최악의 경우 O(n)입니다.