[leetcode] Reveal Cards In Increasing Order

문제

• 문제 링크
• 배열 deck이 주어진다. 배열 안에는 카드 번호가 들어있다. 카드를 정렬한 뒤 아래 순서로 카드를 뽑았을 때 번호가 오름차순으로 뽑힐 수 있게 하려고 한다. 카드를 어떻게 정렬해야 하는지 구해야 한다.
  • 맨 앞에 있는 카드를 뽑고 번호를 확인한 뒤 배열에서 뺀다.
  • 아직 배열에 카드가 남아있다면 맨 앞에 있는 카드를 맨 뒤로 배치한다.
  • 카드가 남지 않을 때까지 위 과정을 반복한다.
• 제약 조건
  • 배열 길이: 1 <= deck.length <= 1000
  • 값 범위: 1 <= deck[i] <= 10^6
  • deck 안에 있는 값들은 모두 unique 하다.

풀이

풀기 전

• 반환해야 하는 배열에 규칙이 있을 거라고 생각해서 예시를 끄적여봤는데 규칙을 찾기가 쉽지 않았다.
• 제약 조건이 빡빡하지 않아서 규칙의 반대로 구현해도 가능할 거 같았다. 그래서 그대로 구현하기로 했다. 주어진 규칙을 거꾸로 구현하면 아래와 같다.
  • 배열이 비어있지 않다면, 맨 뒤에 있는 카드를 맨 앞으로 보낸다.
  • 배열에서 빠진 카드를 가져와서 맨 앞에 배치한다. 기존 규칙에선 오름차순으로 카드 숫자를 뽑기 때문에, 거꾸로 했을 땐 내림차순으로 배치되어야 한다. 즉, 숫자가 큰 카드부터 가져와서 배치한다.
  • 모든 카드를 배치할 때까지 위 과정을 반복한다.
• 배열에 배치한다고 생각하면 복잡할 수 있는데, deque를 사용하면 쉽게 구현할 수 있다. 처음에 직접 연결 리스트를 구현해보고 싶어서 그렇게 풀었는데 코드가 생각보다 길어져서 좀 귀찮았다. 내장된 deque로도 풀어봤는데 확실히 쉽다!

코드

1. 연결 리스트 구현

import java.util.Arrays;
import java.util.Collections;

class Solution {
	// 노드 클래스
    private class Node {
        int val;
        Node prev = null;
        Node next = null;

        public Node(int val) {
            this.val = val;
        }
    }

    public int[] deckRevealedIncreasing(int[] deck) {
        Arrays.sort(deck);  // 숫자가 큰 카드부터 뽑기 위해 정렬한다.
        
        Node head = new Node(0);  // 빈 헤드 노드이다.
        Node last = new Node(deck[deck.length-1]);  // 마지막 카드를 넣어둔다.
        head.next = last;
        last.prev = head;
        for (int i=deck.length-2; i>=0; i--) {
            if (last.prev != head) {  // 마지막 카드만 들어있는 경우엔 건너뛴다.
            	// 1단계: 맨 뒤에 있는 카드를 맨 앞으로 놓는다.
                Node nextLast = last.prev;
                if (nextLast != head)
                    nextLast.next = null;

                if (head.next != last) {
                    last.next = head.next;
                    head.next.prev = last;
                }
                last.prev = head;
                head.next = last;

                last = nextLast;
            }

			// 2단계: 숫자가 큰 카드부터 맨 앞에 배치한다.
            Node newNode = new Node(deck[i]);
            newNode.prev = head;
            newNode.next = head.next;
            head.next.prev = newNode;
            head.next = newNode;
        }

		// 연결 리스트에 있는 값들을 정답에 넣는다.
        int[] ans = new int[deck.length];
        Node now = head.next;
        int idx = 0;
        while (now != null) {
            ans[idx++] = now.val;
            now = now.next;
        }
        return ans;
    }
}

2. deque 사용

import java.util.Arrays;
import java.util.Collections;

class Solution {
    public int[] deckRevealedIncreasing(int[] deck) {
        Arrays.sort(deck);  // 숫자가 큰 카드부터 뽑기 위해 정렬한다.

        Deque<Integer> dq = new LinkedList<>();  // 빈 deque를 만든다.
        for (int i=deck.length-1; i>=0; i--) {
            if (!dq.isEmpty()) {  // deque가 비어있으면 건너뛴다.
                // 1단계: 맨 뒤에 있는 카드를 맨 앞으로 놓는다.
                dq.addFirst(dq.removeLast());
            }
            // 2단계: 숫자가 큰 카드부터 맨 앞에 배치한다.
            dq.addFirst(deck[i]);
        }
        
        // deque에 있는 값들을 정답에 넣어준다.
        int[] ans = new int[deck.length];
        for (int i=0; i<ans.length; i++)
            ans[i] = dq.removeFirst();
        return ans;
    }
}

푼 후

• 연결 리스트 구현하느라 귀찮긴 했는데 그래도 오랜만에 구현해보고 ㅈ..좋았다.
• deck 배열의 길이를 n이라고 하면, deck에 있는 값들을 한 번씩만 순회하긴 하지만 정렬을 하기 때문에 시간 복잡도는 O(nlgn)이다. 값들을 한 번씩 담는 배열과 deque가 있으므로 공간 복잡도는 O(n)이다.