LeetCode알고리즘 Remove Duplicates from Sorted List

LeetCode알고리즘 Remove Duplicates from Sorted List

728x90

반응형

오늘은 83번 문제를 풀어보겠습니다.

EASY고 현재는 47.9%의 성공률을 보이네요.

오늘 주제는 Linked List입니다.

정렬된 링크드 리스트의 헤드가 주어지면, 중복되는 것들을 지워서 각 원소들이 한 번씩만 나타나게 해라.

주어진 예시들을 보겠습니다.

1번 예시를 보면, 1이 2번 나왔잖아요.

그래서 1노드 한 개를 지워줍니다.

지운 결과는 [1,2]이 됩니다.

2번 예시를 보면, 1이 2번 2가 1번, 3이 2번 나왔습니다.

그럼 1노드 1개 지워주고 3노드 1개 지워줘야겠죠.

지운 결과는 [1,2,3]이 됩니다.

문제에서 주어진 제약조건들을 살펴보면

노드의 수, node의 value값, 정렬 보장이 적혀있네요.

마지막 문장이 가장 눈에 띄네요.

일단 정렬이 보장되니까 이 문제는 쉽게 접근할 수 있습니다.

+ 제공해주는 ListNode클래스

/** * Definition for singly-linked list. * public class ListNode { * public var val: Int * public var next: ListNode? * public init() { self.val = 0; self.next = nil; } * public init(_ val: Int) { self.val = val; self.next = nil; } * public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; } * } */

class Solution { func deleteDuplicates(_ head: ListNode?) -> ListNode? { var temp = head while temp?.next != nil { while temp?.val == temp?.next?.val { temp?.next = temp?.next?.next } temp = temp?.next } return head } }

먼저 temp를 생성해줍니다.

while문을 돌면서 temp?.next가 nil이 아닐 때까지 돕니다.

내부에 있는 while문을 통해서 temp?.val이랑 temp?.next?.val이 같으면 temp?.next?.next를 temp?.next에 넣어줍니다.

이 작업을 통해서 값이 같지 않을 때 까지 돌아서 val이 중복되는 노드를 제거하게 됩니다.

(포인팅 하는 노드를 변경하는거니까 제거는 아니고,, 제거된 것 처럼 보이게 함)

그리고 내부의 while을 나오면 temp는 temp?.next로 변경해줍니다.

그리고 head를 리턴해줍니다.

1번 예시 과정ㅋㅋ

(발로 그린 것 같네요,,, ㅈㅅ)

이렇게 했을 때 결과

메모리 사용량 왜그럼?

뭘 많이 사용한 것 같지도 않은데...

+ 추가

class Solution { func deleteDuplicates(_ head: ListNode?) -> ListNode? { var temp = head while temp != nil { if temp?.val == temp?.next?.val { temp?.next = temp?.next?.next } else { temp = temp?.next } } return head } }

이렇게 푸는 방법도 있습니다.

temp?.next = temp?.next?.next 여기를 실행하는 횟수는 위 코드와 동일합니다.

그래서인지 시간 복잡도는 비슷하더라구요.

개인적으로는 처음 작성한 코드가 더 직관적으로 느껴진다고 판단해 윗 방법을 선택했습니다.

resource:

https://leetcode.com/problems/remove-duplicates-from-sorted-list/

728x90

반응형

from http://hyerios.tistory.com/250 by ccl(A) rewrite - 2021-11-11 19:01:14