BOJ - 1021. 회전하는 큐

www.acmicpc.net/problem/1021

1021번: 회전하는 큐

사용할 자료구조

문제에서 "양방향 순환큐" 라고 언급을 하여 양방향으로 삽입/삭제가 모두 가능한 Deque를 사용하였습니다.

 

 

 

문제에서의 3가지 연산

 

1번 연산 : 가장 앞에 있는 원소를 뽑아내는 연산

dq.pop_front();

2번 연산 : 가장 앞에 있는 원소를 뽑아내 가장 뒤로 보내는 연산

dq.push_back(dq.front());

dq.pop();

3번 연산 : 가장 뒤에 있는 원소를 뽑아내 가장 앞으로 보내는 연산

dq.push_front(dq.back());

dq.pop();

 

 

Point

 

1. 항상 맨 앞에 있는 것만 뽑아낼 수 있습니다.

 

2. 2번,3번 연산의 최솟값을 출력해야하므로, 두 연산들 중 어느 것을 선택해야 더 적게 움직일 수 있을지 정해야합니다.

• 찾아야할 수를 Deque 안에서 몇 번째에 있는지 index에 저장해두었습니다.
• index 가 dq.size()- index보다 작다면 2번 연산을 하는 것이 유리합니다. (유리하다 = 더 적게 움직일 수 있다)
• index가 dq.size() - index보다 크다면 3번 연산을 하는 것이 유리합니다.

3. Deque의 맨 앞에 있는 것이 입력받은 수를 찾을 때까지 선택한 연산 작업을 반복해줍니다. 

- 각 연산할 때마다 횟수를 세어줍니다.

- 만약 입력받은 수를 찾는다면 루프에서 탈출하고, 찾았으므로 1번 연산 작업 (dq.pop_front()) 를 수행해주면 완료 됩니다.

- 마지막으로 횟수를 출력해줍니다.

 

시간복잡도

Deque는 삽입/삭제 연산을 앞과 뒤에서만 할 수 있으므로 시간 복잡도는 O(1)

Deque는 탐색 연산을 인덱스를 사용해서 할 수 있으므로 시간 복잡도는 O(1)

 

입력받은 수를 찾을 때까지 루프에서 삽입(push), 삭제(pop) 연산을 하므로, 시간 복잡도는 O(2N) -> O(N) 이라고 볼 수 있다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#include <functional>
using namespace std;
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    deque<int> dq;
    int n,m;
    cin>>n>>m;
    int answer = 0;
    //1~n 까지 초기값
    for(int i=1;i<=n;i++){
        dq.push_back(i);
    }
    for(int i=0;i<m;i++){
        int num;
        cin>>num;
        int index = 0;
        for(int j=0;j<dq.size();j++){
            if(num ==dq[j]){
                index = j;
            }
        }
        if(index < dq.size()-index){
            while(dq.front()!=num){
                dq.push_back(dq.front());
                dq.pop_front();
                answer++;
            }
            dq.pop_front();
        }else{
            while(dq.front()!=num){
                dq.push_front(dq.back());
                dq.pop_back();
                answer++;
            }
            dq.pop_front();
        }
    }
    cout<<answer;
    
    return 0;
}