950-kir3i.md

950. Reveal Cards In Increasing Order

Solution

• 시간복잡도: O(NlogN)

• 알고리즘

  시뮬레이션, 구현

• 풀이설명

  문제에 나온 순서를 역으로 구현하기만 하면 되는 문제입니다. 이 때 C++의 vector나 Python의 list같은 일반적인 array를 이용했다면 카드를 덱의 뒤에서 앞으로 옮기는 과정이 비효율적으로 작동하므로 deque나 queue를 이용하는 게 좋습니다.

• 소스코드

  • C++

    class Solution {
    public:
        vector<int> deckRevealedIncreasing(vector<int>& deck) {
            deque<int> dq;
            sort(deck.begin(), deck.end(), greater<>());
            dq.push_front(deck[0]);
            for(int i=1; i<deck.size(); i++) {
                dq.push_front(dq.back());
                dq.pop_back();
                dq.push_front(deck[i]);
            }
            return vector<int>(dq.begin(), dq.end());
        }
    };

  • Python

    from collections import deque as dq
    
    class Solution:
        def deckRevealedIncreasing(self, deck):
            ans = dq([])
            for x in sorted(deck, reverse=True):
                if ans:
                    ans.appendleft(ans.pop())
                ans.appendleft(x)
            return list(ans)

  • Java

    class Solution {
        public int[] deckRevealedIncreasing(int[] deck) {
            Arrays.sort(deck);
            LinkedList<Integer> dq = new LinkedList<Integer>();
            dq.add(deck[deck.length-1]);
            for(int i=deck.length-2; i>=0; i--) {
                dq.addFirst(dq.pollLast());
                dq.addFirst(deck[i]);
            }
            int[] ans = new int[dq.size()];
            for(int i=0; !dq.isEmpty(); i++)
                ans[i] = dq.poll();
            return ans;
        }
    }