[LeetCode] 83. Remove Duplicates from Sorted List

말하는 감자·2024년 12월 3일

data structure leetcode linked list python 리트코드 연결 리스트 자료구조 코딩테스트 코딩테스트 준비 파이썬

LeetCode

목록 보기

20/32

오늘 문제도 링크드 리스트관련 문제입니다. 이번주까지 리트 코드의 링크드 리스트 문제를 최대한 많이 풀어보려고 합니다.

1. 오늘의 학습 키워드

Linked List

2. 문제: 83. Remove Duplicates from Sorted List

단계: Easy
주제: Linked List
출처: https://leetcode.com/problems/remove-duplicates-from-sorted-list/description/?envType=problem-list-v2&envId=linked-list&difficulty=EASY

Description

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Example 1:

Input: head = [1,1,2]
Output: [1,2]

Example 2:

Input: head = [1,1,2,3,3]
Output: [1,2,3]

Constraints:

The number of nodes in the list is in the range [0, 300].
100 <= Node.val <= 100
The list is guaranteed to be sorted in ascending order.

3. 문제 풀이

Step1. 문제 이해하기

이번 문제는 오름차순으로 정렬된 연결 리스트가 주어졌을 때, 모든 중복되는 노드를 제거하고 한 번만 나오도록 변경한 연결 리스트를 반환하는 문제입니다. 물론, 오름차순은 유지해야 하구요.

연결 리스트의 노드를 순회하면서 중복되면 제거! 이렇게 진행하면 될 것 같습니다. 우선, 문제의 입출력을 살펴보겠습니다.

Input:
- 연결리스트 head가 주어집니다. 주어진 연결 리스트의 노드 개수는 0이상 300개 이하입니다.
- 개수가 매우 적기 때문에 $O(n^2)$ 도 충분히 가능한 문제입니다.
- 하지만 노드를 순회하면서 중복 제거를 진행하기 때문에 $O(n)$ 으로 구성될 것으로 보입니다.
- 연결리스트에 노드가 아예 없을수도 있기 때문에 이것은 예외처리를 진행해야 합니다.
Output:
- 중복 제거가 완료된 오름차순의 연결 리스트를 반환합니다.

Step2. 문제 분석하기

주어진 문제는 연결 리스트의 노드를 순회하면서 현재 노드 값과 다음 노드 값이 같다면 중복되므로, next의 위치를 next의 next로 설정한다면 해결이 가능합니다.

매우 간단히 분석이 완료되었습니다. 바로 코드를 설계해보도록 하겠습니다.

Step3. 코드 설계

설계 내용은 문제 해결을 위한 핵심 단계를 잘 정의하고 있습니다.

예외처리:
- 연결 리스트가 비어 있는 경우 head가 None일 수 있습니다. 이 경우 None을 반환하면 됩니다. 이는 효율적인 예외처리입니다.
노드 순회:
- 현재 노드(curr)를 기준으로 다음 노드가 존재하는지 확인하고, 현재 노드의 값과 다음 노드의 값이 동일한 경우에 다음 노드를 건너뛰는 방식으로 중복을 제거합니다.
- 이렇게 하면 중복 노드를 제거하며 리스트를 수정할 수 있습니다.
시간 복잡도 고려:
- 연결 리스트의 모든 노드를 한 번씩 순회하며 중복을 제거하기 때문에 시간 복잡도는 $O(n)$ 입니다. 효율적입니다.

Step4. 코드 구현

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def deleteDuplicates(self, head):
        # https://leetcode.com/problems/remove-duplicates-from-sorted-list/submissions/1468959575
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if not head:
            return None
        
        curr = head
        while curr:
            while curr.next and curr.val == curr.next.val:
                curr.next = curr.next.next
            curr = curr.next
        return head

코드 설명:
1. 예외 처리:
  - 주어진 연결 리스트가 None인 경우, 즉 비어 있는 경우를 처리합니다. 비어 있는 리스트는 중복 제거할 필요가 없으므로 바로 None을 반환합니다.
2. 현재 노드(curr) 초기화:
  - curr 변수를 생성하여 head를 저장합니다. 이를 통해 연결 리스트를 순회하며 중복 노드를 제거합니다.
3. 연결 리스트 순회 (while curr):
  - curr가 None이 아닐 때까지 반복합니다. 이는 연결 리스트의 모든 노드를 방문하는 과정입니다.
  - 각 노드에서 중복 여부를 확인하고, 필요한 경우 제거합니다.
4. 중첩 루프:
  - curr.next와 curr.val == curr.next.val 조건을 동시에 확인합니다.
    - curr.next가 존재하지 않으면 더 이상 비교할 노드가 없으므로 중첩 루프를 종료합니다.
    - 현재 노드의 값(curr.val)과 다음 노드의 값(curr.next.val)이 같으면 중복이므로 제거해야 합니다.
  - 중복 제거는 curr.next를 curr.next.next로 설정하여 이루어집니다. 이렇게 하면 현재 노드의 next가 다음 노드가 아닌 그다음 노드를 가리키게 되어 중복 노드가 리스트에서 제외됩니다.
5. 현재 노드 이동:
  - 중첩 루프에서 중복 제거가 완료된 후, 현재 노드(curr)를 다음 노드로 이동시켜 순회를 계속합니다.
  - 이를 통해 모든 중복을 제거한 후 리스트의 끝까지 탐색합니다.
6. 결과 반환:
  - 순회를 마치면 중복 제거가 완료된 연결 리스트의 시작 노드(head)를 반환합니다.
시간 복잡도:
- 시간 복잡도: $O(n)$
  - 연결 리스트의 모든 노드를 한 번씩 방문하며 중복 여부를 확인하므로 시간 복잡도는 $O(n)$ 입니다.
  - 이때, n은 연결 리스트의 노드 개수를 나타냅니다.
- 공간 복잡도: $O(1)$
  - 주어진 연결 리스트를 그대로 수정하며 별도의 추가 공간을 사용하지 않으므로 공간 복잡도는 $O(1)$ 입니다.
결과: https://leetcode.com/problems/remove-duplicates-from-sorted-list/submissions/1468959575

4. 마무리

이번 문제는 정렬된 연결 리스트에서 중복을 제거하는 기본적인 문제로, 연결 리스트의 순회와 노드 삭제와 같은 기초적인 조작 방법을 학습하는 데 효과적입니다. 이번 문제를 통해 Linked List의 구조와 조작 방식에 대한 이해를 더욱 확장할 수 있었습니다. 다음 문제에서는 더 복잡한 연결 리스트 문제를 도전하며 학습을 이어가겠습니다. 🚀

테스트 케이스를 돌리는 전체 코드는 다음 링크에서 확인할 수 있습니다.

읽어주셔서 감사합니다!