CTCI | 중복 없애기

Cracking the Coding Interview

 

문제: 정렬되어있지 않은 Linked List에서 중복되는 원소를 제거하는 코드 작성하기

우선 Linked List의 특징은, head에 대한 포인트를 갖고 시작한다는것과, 사이즈가 얼마나 될지 알지 못한다는 것이다. 이 문제를 풀 수 있는 가장 간단한 방법은, Set을 사용해서 지금까지 등장한 원소들을 저장해가면서, 만약 Set에 없다면, Set에 추가하고 넘어가고, 만약, Set에 존재한다면, 그 해당 노드를 건너뛰는 방식으로 진행할 수 있다. 여기서 또 한가지 생각해야하는것은 Deletion과 Edge케이스이다. 먼저, Delete를 어떻게 해나갈지, LinkedList를 그려가며 생각해보자.

head 노드에서 2번 이동한 노드가, 중복 노드라고 할 때, 이 노드를 삭제하려면 어떻게 해야할까?

바로 이전노드의 next를 현재 노드의 next로 지정해주면 된다. 즉, 포인트는 우리가 고민할 노드의 그 전 노드를 가르키고, 그 다음 노드를 확인하는식으로 진행하면 된다.

 

시작과 끝, 그리고 Efficiency

그러면 이 코드의 시작과 끝은 어떻게 정할까? 먼저 어떤 세팅으로 시작할지 생각해보자. 먼저 어떠한 loop을 돌기 전에, Set을 만들어 head의 값을 저장한채 시작한다. 그리고 loop을 돌리면서 지금 현재 노드의 다음노드가 null일 때, 이 loop을 종료하면 된다. 그렇다면, 시작을 아예 못하는 경우는 없을까? 있다. head노드가 null이라면? 우리는 비어있는 노드를 그대로 리턴하면 된다. 이렇게 시작과 끝, 그리고 그 안에 있는 edge case까지 생각해봤으니, 이 알고리즘이 속도면으로나 공간적으로 타당한지 생각해보자.

 

우선, 이 알고리즘으로는 LinkedList의 처음과 끝까지, N개의 노드만큼 연산을 해야한다. 그러므로 O(N)의 Time Complexity라고 할 수 있다. 그리고 HashSet의 경우는? 중복이 있을 경우는 0개부터 N개까지(모든 노드가 중복) 다양하다. 그렇다면 BigO는 어떻게 구할 수 있을까? 모든 값을 더하고, N으로 나눠주면 되는데, 그것은 아래와 같다.

(0 + 1 + 2 + ... + N) = N(N + 1)/2

 

이제 이것을 N 으로 나누어주게 되면, (N + 1) / 2 가 되고, BigO에서 Constants는 제외하고 생각하기 때문에, 공간, Space Complexity또한 O(N)이 된다. 합리적인 연산으로 생각이 되기 때문에, 위에서 생각했던 방식으로 코딩을 진행한다. 먼저, Node 클래스는 다음과 같다고 가정한다.

Class Node {
    Node next;
    int val;
}

 

그리고 실제 해법은 다음과 같다.

import java.util.Set;

class Solution {

    public Node removeDuplicate(Node head){
    	if(head == null){
        	return null;
        }
        
        Set<Integer> set = new HashSet<>();
        set.add(head.val);
        
        Node curr = head;
        
        while(curr.next != null){
        	if(set.contains(curr.next.val){
            	curr.next = curr.next.next;
            } else {
            	set.add(curr.next.val);
                curr = curr.next;
            }
        }
        
        return head;
    }
}

 

 

그런데 만약, Set과 같은 공간을 쓰지 못하면 어떻게 풀어야할까?

 

시간복잡도(Time Complexity)는 늘겠지만, O(N^2)으로, 두개의 포인터를 사용해서, 하나는 중복을 가려내기 위해 한 노드를 포인트하고, 다른 한 노드는 그 노드보다 next에 위치한 모든 노드들을 스캔하면서 같은 노드가 있을 시, 지워내는 역할을 해야한다. 코드는 다음과 같다.

 

public Node removeDupNoSet(Node head){
        if(head == null){
            return null;
        }

        Node curr = head;
        while(curr != null){
            Node runner = curr;
            while(runner.next != null){
                if(curr.val == runner.next.val){
                    runner.next = runner.next.next;
                } else {
                    runner = runner.next;
                }
            }
            curr = curr.next;
        }

        return head;
    }

 

 

 

Reference

해법: https://github.com/g471000/data-algorithm-study/blob/master/ctci/src/ch_02_linked_list/Q1.java

data-algorithm-study/ctci/src/ch_02_linked_list/Q1.java at master · g471000/data-algorithm-study

 

CTCI Github: https://github.com/careercup/CtCI-6th-Edition/tree/master/Java/Ch%2002.%20Linked%20Lists/Q2_01_Remove_Dups

CtCI-6th-Edition/Java/Ch 02. Linked Lists/Q2_01_Remove_Dups at master · careercup/CtCI-6th-Edition