백준 1021번 : 회전하는 큐 | queue, deque [C++]

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

1021번: 회전하는 큐

처음엔 queue로 접근하였지만 인덱스 접근이 불가능하므로 deque 사용을 시도하였다.

풀이법

1. 큐 연산 구현하기

    a. 첫 번째 원소를 뽑아낸다. => pop_front() 사용

    b. 왼쪽으로 한 칸 이동시킨다. => push_back()으로 front()값 맨 뒤에 넣고, 뒤로 옮긴 값 pop_front()으로 삭제

    c. 오른쪽으로 한 칸 이동시킨다. => push_front()로 back()값 맨 앞에 넣고, 앞으로 옮긴 값 pop_back()으로 삭제

2. 어떤 경우에 어떤 연산을 사용하는 가?

    1번. q.front() == input_n 첫 원소와 입력받은 값이 같은 경우 다른 연산없이 바로 pop

    2번. index < (q.size() - index) : 이때, index는 입력받은 수의 큐에서의 인덱스이다.  인덱스가 큐 사이즈 - 원소 위치보다             작다면 원소가 앞쪽에 위치한 것이므로 2번연산이 효율적.

           ex) 큐가 1 2 3 4 5 일때, input_n = 2 , index = 2 , q.size() - index = 5 - 2 = 3  ==> index < 3 

    3번. index >= (q.size() - index) : 큐 사이즈 - 원소 위치가 자신의 위치 보다 크다면 뒷쪽에 위치한 것이므로 3번 연산 실행

        ex) 1 2 3 4 5 라고 할때, input_n = 4 , index =4 이므로 q.size() - index = 5 - 4 = 1 ==> index > 1 

 

전체코드

#include <iostream>
#include <deque>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    deque<int> q; //연산을 진행할 큐
    int N; //큐의 크기
    int index; //2,3번 연산을 선택하기 위한 인덱스 정보
    int cnt = 0; //2,3번 연산 횟수

    cin >> N;
    for (int i=0; i < N;i++) { //1~N을 큐에 추가
        q.push_back(i+1);
    }
    int M;
    cin >> M;
    
    int input_n; //입력받는 수
    for (int i = 0; i < M; i++) {
        cin >> input_n;
        for (int idx = 0; idx < q.size(); idx++) { 
            //0부터 시작하니까 전위 연산자로 +1된 값을 저장함
            if(q[idx] == input_n) {
                index = idx;
                break;
            }
        }
        while(true) { //큐 연산
            
            if (q.front() == input_n) { //큐의 첫번째 원소가 n이라면 pop
                q.pop_front();
                break;
            }
            else {
                if (index < (q.size()- index)) { 
                    //해당 원소보다 뒤의 요소가 더 많다는 뜻 => 2번 연산이 효율적
                    cnt++;
                    q.push_back(q.front()); //첫번째 값을 마지막에 추가하고
                    q.pop_front(); //첫번째 값 삭제
                }
                else {
                    cnt++;
                    q.push_front(q.back()); //마지막 값을 맨 앞에 추가
                    q.pop_back(); //마지막 값 삭제
                }
            }
            if (q.size() == 0) {
                break;
            }
        }
    }

    cout << cnt << " ";
    
	return 0;
}

 

+ queue vs deque 개념정리

#include <queue>

queue<int> q; //queue 선언

q.front(); //맨 앞 요소
q.back(); //맨 뒤 요소

q.push(0); //맨 뒤에 0 추가

q.pop(); //맨 뒤 요소 삭제

q.at(3); //인덱스 3에 접근
q.size(); //queue의 크기
q.empty(); //큐가 비어있는지 확인

#include <deque>

deque<int> dq; //deque 선언

dq.front(); //맨 앞 요소
dq.back(); //맨 뒤 요소

dq.push_front(0); //맨 앞에 0 추가
dq.push_back(1); //맨 뒤에 1 추가

dq.pop_front(); //맨 앞 요소 삭제
dq.pop_back(); //맨 뒤 요소 삭제

dq.at(3); //인덱스 3에 접근
dq.size(); //queue의 크기
dq.empty(); //큐가 비어있는지 확인