[LeetCode] 950. Reveal Cards In Increasing Order

https://leetcode.com/problems/reveal-cards-in-increasing-order/description/

Leetcode - Reveal Cards In Increasing Order

문제 유형 : 스택, 큐

문제 난이도 : Medium

 

문제

You are given an integer array deck. There is a deck of cards where every card has a unique integer. The integer on the ith card is deck[i].

You can order the deck in any order you want. Initially, all the cards start face down (unrevealed) in one deck.

You will do the following steps repeatedly until all cards are revealed:

1. Take the top card of the deck, reveal it, and take it out of the deck.
2. If there are still cards in the deck then put the next top card of the deck at the bottom of the deck.
3. If there are still unrevealed cards, go back to step 1. Otherwise, stop.

Return an ordering of the deck that would reveal the cards in increasing order.

Note that the first entry in the answer is considered to be the top of the deck.

 

정수 배열 deck이 주어집니다. 카드들이 deck배열에 중복없는 정수들로 이루어집니다.

i번째 카드의 번호는 deck[i]입니다.

 

당신은 덱을 마음대로 섞어도됩니다.

처음에, 모든 카드들은 아래로 뒤집어져 있습니다.

당신은 아래의 과정으로 모든 카드를 펼쳐야 합니다.

 

1. 덱의 맨 위 카드를 뒤집어 깝니다. 그리고 덱에서 뺍니다.
2. 아직 카드가 더 있으면, 다음 맨 위의 카드를 뺴서 덱의 아래로 넣습니다.
3. 만약 아직 펼쳐지지 않은 카드가 있다면, 1부터 반복합니다.

 

오름차순으로 카드가 개방되도록 카드를 배열하시오. 

정답 배열의 맨 앞이 덱의 맨 위입니다.

 

풀이

deque를 이용하여 카드를 펼치는 과정의 역순을 따르는 방법이 있고,

queue를 이용하여 적절한 위치에 숫자를 끼워넣는 방법이 있습니다.

 

데크를 이용하면 맨 앞에 숫자를 추가하고, 맨 뒤 숫자를 빼서 맨 앞으로 옮기는 식으로 하면 되고,

큐를 이용하면 큐에 인덱스를 오름차순으로 저장했다가, 큐로 카드를 펼치는 과정을 그대로 하면 됩니다.

정답배열의 인덱스로 큐에서 뽑은 인덱스의 카드값을 넣으면 됩니다.

큐 부분이 이해가 안 되실 수도 있지만, 아래의 시각화를 보시면 이해되실 겁니다.

 

 

코드

C++ - 데크를 이용한 풀이

class Solution {
public:
    vector<int> deckRevealedIncreasing(vector<int>& deck) {
        sort(deck.begin(), deck.end(), greater<int>());
        deque<int> dq;
        vector<int> ans;
        int i;

        for(i = 0; i < deck.size()-1; i++) {
            dq.push_front(deck[i]);

            auto lastCard = dq.back();
            dq.pop_back();

            dq.push_front(lastCard);
        }
        dq.push_front(deck[i]);

        while(!dq.empty()) {
            auto card = dq.front();
            dq.pop_front();

            ans.push_back(card);
        }

        return ans;
    }
};

 

C++ - 큐를 이용한 풀이

class Solution {
public:
    vector<int> deckRevealedIncreasing(vector<int>& deck) {
        int n = deck.size();
        sort(deck.begin(), deck.end());
        queue<int> q;
        for(int i = 0; i < n; i++) {
            q.push(i);
        }
        vector<int> ans(n);
        for(int i = 0; i < n; i++) {
            int idx = q.front();
            q.pop();
            
            q.push(q.front());
            q.pop();
            ans[idx] = deck[i];
        }
        return ans;
    }
};