Reveal Cards in Increasing Order

문득 구현 문제를 찾던 와중에 내가 원하는 스타일에 구현 문제가 안나와서 헤매고 있었다가 몸 풀기로 오랜만에 리트코드 문제를 풀어보고 싶었다. 문제 자체 정답률이 70을 넘어가기에 쉬운 문제이겠다 싶어서 문제를 읽고 있었는데...이걸 어떻게 풀지? 하는 생각이 들었다.

정답률에 반대로 솔직히 생각할게 많고 당장 문제를 읽자마자 답이 떠오를만한 그런 문제는 정말 아니였다. 오늘 다른 사람의 블로그를 읽으면서 deque 에 관한 글을 읽었는데 내가 한번도 사용하지 않았던 자료구조였지만 한번 써봐야겠다는 생각이 들었는데 이 문제에 쓸줄 몰랐다.

문제 예시가 굉장히 자세히 적혀있는데 저 구성을 그대로 구현화 해서 deque 를 써보았다. 정말로 처음 써보는거라 신기했는데 일반적인 queue 가 아니고

push_front(), pop_front(), pop_back() 등등 indexing 또한 가능하게 해주는 자료구조 였다. 이런 식의 문제는 보통 "카드" 관련 문제에서 많이 쓰이던데 앞으로도 알고는 있어야겠다.

class Solution {
public:
    vector<int> deckRevealedIncreasing(vector<int>& deck) {
        vector<int> answer; 
        sort(deck.begin(),deck.end()); 
        deque<int> deq; 
        deq.push_back(deck.back()); 
        deck.pop_back(); 
        
        while(!deck.empty()){
            int save = deq.back(); 
            deq.pop_back(); 
            deq.push_front(save);
            deq.push_front(deck.back()); 
            deck.pop_back(); 
        }
        
        for(int &n : deq){
            answer.push_back(n); 
        }
        
        
        return answer; 
    }
};

문제 자체는 어렵지는 않았고 디큐 자료구조를 안 후에는 문제 예시를 그대로 구현 해주었다. 그래도 이 문제를 보고 바로 아이디어가 떠오를거 같지는 않았다.

배운점:
1. deque에 활용
2. sorting 시물레이션