[C++] 백준 1021- 회전하는 큐

 

https://www.acmicpc.net/problem/1021

1021번: 회전하는 큐

<알고리즘 분류>

   - 자료구조(Data Structure)

   - 덱(Deque)

 

<풀이> 

  1. C++에서 배열을 지원하는 컨테이너로 대표적인 <vector> 가 있지만, 문제를 보면 양쪽에서 pop과 push를 해야하는 상황이므로 배열을 더 유연하게 다룰 수 있는 <deque>를 쓰기로 했다.

 

<주의사항>

  1. 문제 이해가 우선이다. 1~N까지 적혀 있는 카드들을, 한꺼번에 왼쪽으로 밀거나 오른쪽으로 옮기면서 순서대로 원하는 카드들을 뽑는다는 것을 이해해야 한다. 

  2.

 if (index < dq.size() - index + 1)

위의 if문을 적는 것이 이 문제의 포인트다. 왼쪽으로 이동하는 것이 나을지, 오른쪽으로 이동하는 것이 나을지를 판단하는 if문이다. 

 

<코드>

#include <iostream>
#include <algorithm>
#include <deque>
#include <cstring>

using namespace std;

int N, M;
int GetNum[50];
int num[50];
deque <int> dq;

int main(){
    
    cin >> N >> M;
    int cnt =0;

    for (int j=1; j<=N; j++){
            dq.push_back(j); // 최초의 덱 만들기
        }
    for (int i=0 ; i< M ; i++){
        cin >> GetNum[i];  // 추출해야하는 수를 받기


        int index;
        for (int k = 0; k < dq.size(); ++k) {
			if (dq[k] == GetNum[i]) {
				index = k;
				break;
			}
        } //GetNum의 index 찾기
        int tmp ;
        if (index < dq.size() - index + 1){
            //왼쪽
            
            while(1){
                //왼쪽으로 한 칸 이동 : 
                tmp = dq.front();
                if (tmp == GetNum[i]) 
                {   
                    dq.pop_front();
                    break;
                } 
                cnt ++;
                dq.pop_front();
                dq.push_back(tmp);
            }

        }

        else{

            while(1){
                //오른쪽으로 한 칸 이동:
                tmp = dq.back();
                cnt ++;
                dq.pop_back();
                dq.push_front(tmp);
                if (tmp == GetNum[i]) 
                {   
                    dq.pop_front();
                    break;      
                }
            }
        }

    }

    cout << cnt ;

}