[Java] LeetCode 1206: Design Skiplist

[문제 바로 가기] - Design Skiplist

문제 해석

여러 층의 정렬된 연결 리스트인 Skip list를 내장 라이브러리를 사용하지 않고 직접 구현하는 문제다.

아래층으로 갈수록 노드가 많고, 위층에서는 일부 노드만 뽑아서 빠른 길을 탐색할 수 있도록 한다. 이러한 구조 덕분에 삽입, 삭제, 탐색 연산을 평균적으로 O(log n) 시간에 수행할 수 있으며, 공간 복잡도는 O(n)이 된다.

• Skiplist() : Skiplist 객체 초기화
• bool search(int target) : 정수 target이 Skiplist에 존재하면 true, 그렇지 않으면 false 반환
• void add(int num) : 값 num을 Skiplist에 삽입
• bool erase(int num) : 값 num을 Skiplist에서 제거하고, 제거에 성공하면 true 반환
  num이 Skiplist에 존재하지 않으면 아무 동작도 하지 않고 false 반환
  동일한 값 num이 여러 개 존재하는 경우, 그중 하나만 제거해도 됨

---

💡 아이디어

처음 접해보는 자료구조기도 하고, 동작 방식이 잘 이해가 되지 않아 일단 개념을 익힐 겸 코드를 작성해보기로 했다.

처음 풀이 (599ms, 통과했지만 틀린 코드)

Skip list는 탐색, 삭제, 삽입 연산에서 모두 적절한 위치를 찾아야 한다. 정렬된 상태를 유지해야 하기 때문이다.

오른쪽으로 계속 이동하면서 찾는 위치가 해당 층(layer)에 없을 경우에는 아래층으로 내려가야 한다. 따라서 Node는 right와 down이라는 값을 갖고 있어야 한다. 하지만 이 풀이에서는 down이 필요하지 않다. 이 부분은 뒤에서 다시 이야기하겠다.

📌 Node 클래스

	class Node {
        int val;
        Node right;
        Node down;

        Node(int val, Node right, Node down) {
            this.val = val;
            this.right = right;
            this.down = down;
        }
    }

📌 생성자 및 필드

가장 위의 레벨의 노드인 head를 선언해주고, 생성자에서 head를 초기화해준다.

head는 더미 헤드이므로, 값은 -1, right와 down은 null로 넣어준다. level은 1로 초기화 시켜주었는데, 이 부분도 뒤에서 다시 이야기하겠다.

    private Node head; // 가장 위 레벨의 더미 헤드
    private int levels; // 현재 레벨

    public Skiplist() {
        head = new Node(-1, null, null);
        levels = 1;
    }

📌 search()

    public boolean search(int target) {
        Node cur = head;

        while (cur != null) {
            while (cur.right != null && cur.right.val < target) {
                cur = cur.right;
            }

            if (cur.right != null && cur.right.val == target) return true;

            cur = cur.down;
        }

        return false;
    }

cur을 head로 지정한 후, 먼저 오른쪽으로 이동하면서 값을 탐색한다. 찾아야 하는 값인 target보다 작을 경우와 cur.right가 null이 아닐 경우 계속해서 오른쪽으로 이동한다.

만약 그 전에 target 값과 일치하는 값을 찾는다면 바로 true를 반환해준다.

이 과정에서 target 값을 찾지 못한다면 cur = cur.down으로 아래층으로 이동해준다. 만약 끝까지 찾지 못한다면 false를 반환한다.

📌 add()

    public void add(int num) {
        Node cur = head;

        // cur의 오른쪽으로 이동하면서 가장 끝과 적절한 위치(값에 따른) 찾기
        while (cur.right != null && cur.right.val < num) {
            cur = cur.right;
        }

        Node node = new Node(num, cur.right, null);
        cur.right = node;
    }

add()도 search()와 비슷한데, cur의 오른쪽으로 계속해서 이동하면서 삽입해야 할 적합한 위치를 먼저 찾는다.

적절한 위치를 찾았다면, 새 노드인 node를 생성하여 cur.right에 node를 대입해준다.

📌 erase()

    public boolean erase(int num) {
        Node cur = head;
        boolean isFound = false;

        while (cur != null) {
            while (cur.right != null && cur.right.val < num) {
                cur = cur.right;
            }

            if (cur.right != null && cur.right.val == num) {
                cur.right = cur.right.right;
                isFound = true; // 모든 레벨에서의 num을 지워야하므로
            }

            cur = cur.down;
        }

        return isFound;
    }

erase()도 add(), search()와 비슷한데, 모든 층에 있는 num을 지워야 하고, 해당하는 값이 없다면 false를 반환해줘야 하므로 구조가 조금 다르다.

위의 코드들과 같이 cur이 계속 오른쪽으로 이동하면서 일치하는 값이 나타나면 해당 값을 cur.right = cur.right.right로 지워주고(연결을 끊어준다고 생각하면 된다) isFound를 true로 바꿔준다. 이때 바로 true를 반환하지 않는 이유는 모든 층에 있는 num을 지워야 하기 때문이다. (참고로 각 층에 있는 모든 num을 지우는 것은 아니다. 문제에서 같은 값이 있더라도 하나만 제거해도 된다고 함)

이후 아래층으로 이동하면서 계속 num 값과 같은 값들을 찾아준다.

마지막에 isFound를 반환함으로써 num에 해당하는 값이 있었는지를 알려준다.

📌 전체 코드

import java.util.*;

class Skiplist {
    class Node {
        int val;
        Node right;
        Node down;

        Node(int val, Node right, Node down) {
            this.val = val;
            this.right = right;
            this.down = down;
        }
    }

    private Node head; // 가장 위 레벨의 더미 헤드

    public Skiplist() {
        head = new Node(-1, null, null);
        levels = 1;
    }
    
    public boolean search(int target) {
        Node cur = head;

        while (cur != null) {
            while (cur.right != null && cur.right.val < target) {
                cur = cur.right;
            }

            if (cur.right != null && cur.right.val == target) return true;

            cur = cur.down;
        }

        return false;
    }
    
    public void add(int num) {
        Node cur = head;

        // cur의 오른쪽으로 이동하면서 가장 끝과 적절한 위치(값에 따른) 찾기
        while (cur.right != null && cur.right.val < num) {
            cur = cur.right;
        }

        Node node = new Node(num, cur.right, null);
        cur.right = node;
    }
    
    public boolean erase(int num) {
        Node cur = head;
        boolean isFound = false;

        while (cur != null) {
            while (cur.right != null && cur.right.val < num) {
                cur = cur.right;
            }

            if (cur.right != null && cur.right.val == num) {
                cur.right = cur.right.right;
                isFound = true; // 모든 레벨에서의 num을 지워야하므로
            }

            cur = cur.down;
        }

        return isFound;
    }
}

제출 후 성공을 받았지만 이 코드는 Skip list의 정확한 구조를 나타내지 못한 틀린 코드이다.

그 이유는 1. down이 구현되지 않음 2. 내부 레벨 존재하지 않음 3. 랜덤 분포 없음 이 세가지이다.

이 문제에서는 구조를 검사하지 않고 오직 search(), add(), erase()의 결과만 검사하기 때문에 위와 같은 코드가 통과할 수 있는 것이다.

결국 내 코드는 Skip list가 아닌 정렬된 단일 연결 리스트라고 할 수 있는 것이다.

최종 풀이 (526ms)

처음 풀이와 다른 부분은 다음과 같다.

📌 필드

	static final int MAX_LEVEL = 16;
    Random rand = new Random();

먼저 필드에 최대 레벨과 Random 필드가 생겼다. 어디에 쓰이는 값들인지는 뒤에서 이야기하겠다.

📌 add()

    public void add(int num) {
        Node cur = head;
        Node[] update = new Node[MAX_LEVEL];

        // 1️⃣ 위에서 아래로 이동하면서 각 레벨별 num을 삽입해야 할 위치 기록
        for (int i = levels - 1; i >= 0; i--) {
            while (cur.right != null && cur.right.val < num) {
                cur = cur.right;
            }

            update[i] = cur;
            cur = cur.down;
        }

        // 2️⃣ 랜덤 레벨 결정
        int randomLvl = randomLevel();

        // 랜덤 레벨이 현재 Skip list의 높이보다 높을 경우
        if (randomLvl > levels) {
            for (int i = levels; i < randomLvl; i++) {
                // head를 부족한 수만큼 만들어서 레벨을 추가해줌
                head = new Node(-1, null, head);
                update[i] = head;
            }

            levels = randomLvl;
        }
		
        // 3️⃣ 새 노드 삽입 및 down 연결
        Node downNode = null; // 바닥 레벨의 down이 될 노드
        for (int i = 0; i < randomLvl; i++) {
            Node newNode = new Node(num, update[i].right, downNode);
            update[i].right = newNode;
            downNode = newNode;
        }
    }

search()와 erase() 메서드는 이전 코드와 같지만 add() 메서드가 많이 바뀌었다.

1️⃣ 먼저 update라는 Node 배열이 추가되었는데, 이 배열에는 각 레벨별로 num을 삽입해야 할 위치를 저장한다. 즉, update[i]에 i번째 레벨에서 num이 추가될 노드의 왼쪽 노드가 저장되는 것이다.

2️⃣ randomLevel()에서 랜덤으로 레벨을 받아오는데, 랜덤 레벨이 현재 Skip list의 높이인 levels보다 클 경우에는 head 부족한 만큼 만들어서 레벨을 추가해준다. 이때 update 배열도 갱신해주면서 각 레벨에 num이 어디에 추가되어야 할지 저장한다.

3️⃣ 미리 기록해 둔 update 노드의 오른쪽에 값이 num인 새 노드를 삽입하고, 이전에 생성한 노드를 down 포인터로 연결한다. 이때 downNode는 바닥 레벨, 즉 레벨이 0인 노드의 down이 될 노드이다.

📌 전체 코드

import java.util.*;

class Skiplist {
    static final int MAX_LEVEL = 16;
    Random rand = new Random();

    class Node {
        int val;
        Node right;
        Node down;

        Node(int val, Node right, Node down) {
            this.val = val;
            this.right = right;
            this.down = down;
        }
    }

    private Node head; // 가장 위 레벨의 더미 헤드
    private int levels; // 현재 레벨

    public Skiplist() {
        head = new Node(-1, null, null);
        levels = 1;
    }
    
    public boolean search(int target) {
        Node cur = head;

        while (cur != null) {
            while (cur.right != null && cur.right.val < target) {
                cur = cur.right;
            }

            if (cur.right != null && cur.right.val == target) return true;

            cur = cur.down;
        }

        return false;
    }
    
    public void add(int num) {
        Node cur = head;
        Node[] update = new Node[MAX_LEVEL];

        // 위에서 아래로 이동하면서 각 레벨 별 num을 삽입해야 할 위치 기록
        for (int i = levels - 1; i >= 0; i--) {
            while (cur.right != null && cur.right.val < num) {
                cur = cur.right;
            }

            update[i] = cur;
            cur = cur.down;
        }

        // 랜덤 레벨 결정
        int randomLvl = randomLevel();

        // 랜덤 레벨이 현재 Skip list의 높이보다 높을 경우
        if (randomLvl > levels) {
            for (int i = levels; i < randomLvl; i++) {
                // head를 부족한 수만큼 만들어서 레벨을 추가해줌
                head = new Node(-1, null, head);
                update[i] = head;
            }

            levels = randomLvl;
        }

        Node downNode = null; // 바닥 레벨의 down이 될 노드
        for (int i = 0; i < randomLvl; i++) {
            Node newNode = new Node(num, update[i].right, downNode);
            update[i].right = newNode;
            downNode = newNode;
        }
    }
    
    public boolean erase(int num) {
        Node cur = head;
        boolean found = false;

        while (cur != null) {
            while (cur.right != null && cur.right.val < num) {
                cur = cur.right;
            }

            if (cur.right != null && cur.right.val == num) {
                cur.right = cur.right.right; // 링크 끊기
                found = true; // 모든 레벨에서의 num을 지워야하므로
            }

            cur = cur.down;
        }

        return found;
    }

    // 삽입 시 랜덤으로 삽입하기 위해 사용하는 메서드
    private int randomLevel() {
        int level = 1;

        while (level < MAX_LEVEL && rand.nextBoolean()) {
            // rand.nextBoolean()은 true 또는 false를 랜덤으로 반환 = 동전 던지기
            level++;
        }

        return level;
    }
}

실행 시간 줄인 다른 풀이 (26ms)

class Skiplist {
    class Node {
        int val;
        Node[] next; // 배열 포인터 방식
        
        Node(int val, int level) {
            this.val = val;
            next = new Node[level];
        }
    }
    
    Node head;
    Random rand;
    int maxLevel = 16;
    
    public Skiplist() {
        head = new Node(-1, maxLevel);
        rand = new Random();
    }
    
    public boolean search(int target) {
        Node cur = head;
        
        for (int i = maxLevel - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < target) {
                cur = cur.next[i];
            }
        }
        
        cur = cur.next[0];
        return cur != null && cur.val == target;
    }
    
    public void add(int num) {
        Node[] update = new Node[maxLevel];
        Node cur = head;
        
        for (int i = maxLevel - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < num) {
                cur = cur.next[i];
            }
            update[i] = cur;
        }
        
        int level = randomLevel();
        Node newNode = new Node(num, level);
        
        for (int i = 0; i < level; i++) {
            newNode.next[i] = update[i].next[i];
            update[i].next[i] = newNode;
        }
    }
    
    public boolean erase(int num) {
        Node[] update = new Node[maxLevel];
        Node cur = head;
        
        for (int i = maxLevel - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < num) {
                cur = cur.next[i];
            }
            update[i] = cur;
        }
        
        cur = cur.next[0];
        
        if (cur == null || cur.val != num) return false;
        
        for (int i = 0; i < maxLevel; i++) {
            if (update[i].next[i] != cur) break;
            update[i].next[i] = cur.next[i];
        }
        
        return true;
    }
    
    int randomLevel() {
        int level = 1;
        
        while (level < maxLevel && rand.nextDouble() < 0.5) {
            level++;
        }
        
        return level;
    }
}

내 풀이가 너무 오래 걸려서 (526ms) 빠른 풀이 중 정답 수가 가장 많은 풀이(26ms)를 찾아보았다. 차이점은 다음과 같다.

1️⃣ Node 배열 사용

• 나의 경우에는 Node의 down, right를 사용해서 포인터를 따라갔는데, Node 배열을 사용한다면 훨씬 더 빠른 접근이 가능하다.
  (왜 이 경우 더 빠른지는 배열과 연결 리스트의 접근 속도를 공부하면 좋을 것이다.)
• search()에서 특히 right -> right -> down와 같은 탐색이 많은데, 배열을 사용하게 되면 캐시 친화적이기 때문에 속도가 줄어들 수 밖에 없다.

2️⃣ 객체 생성 횟수의 차이

• 내 풀이는 down 연결을 위해 Node 객체를 여러개 생성하는데, 이 풀이에서는 newNode 하나만 생성하고 next 배열을 통해 연결한다.

3️⃣ 레벨 관리

• 나는 head를 동적으로 늘리고 down을 연결하는 과정이 필요하다. 반면 이 코드는 head는 항상 maxLevel로 고정되어 있고, 레벨의 감소나 증가를 고려할 필요가 없다.

리트코드에서는 많은 테스트 케이스를 실행시킬 것이므로 이러한 차이에서 실행 시간이 이렇게 크게 차이나지 않나 싶다.