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

✏️  문제 링크

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

✏️ 문제 설명

✏️ 로직

입력받는 값을 저장할 queue와 위치를 저장할 deque를 생성한다.

queue의 길이만큼 반복문을 돌려서 지민이가 뽑아내려고 하는 원소를 뽑는 데 걸리는 연산의 횟수를 더한다

fun함수

• q.front()를 인수로 받아서 만약 dq.front() == q.front()라면 연산 횟수를 return
• deque안에서 q.front()의 위치(pos2)가 어디인지 구한다 ⇒ findValuePos함수 구현
• 만약 pos2가 deque의 중간보다 왼쪽에 있다 ⇒ 문제에서 주어진 2번 연산 수행
• 만약 pos2가 deque의 중간보다 오른쪽에 있다 ⇒ 문제에서 주어진 1연 연산 수행
• 단, deque.size()가 홀수인 상황에서 pos2가 deque의 중간값이라면 왼쪽 연산을 수행

✏️ 코드

#include<bits/stdc++.h>
using namespace std;

queue<int> q;
deque<int> dq;

int findValuePos(int target) {
    int pos = 1;
    for (auto it = dq.begin(); it != dq.end(); it++) {
        if (*it == target)
            return pos;
        pos++;
    }
}

int fun(int pos) {
    int cal = 0;
    while (!dq.empty()) {
        if (pos == dq.front()) {
            dq.pop_front();
            return cal;
        }
        
        int pos2 = findValuePos(pos); 
        int size = dq.size(); 
        if (((size/2)+1 == pos2 && size % 2 == 1) || (size / 2 >= pos2 ))  {

            while (true) {
                if (pos == dq.front()) {
                    dq.pop_front();
                    return cal;
                }
                int num = dq.front();
                dq.pop_front();
                dq.push_back(num);
                cal++;
            }
        }
        
        while (true) {
            if (pos == dq.front()) {
                dq.pop_front();
                return cal;
            }
            int num = dq.back();
            dq.pop_back();
            dq.push_front(num);
            cal++;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, pos, cal = 0;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        cin >> pos;
        q.push(pos);
    }

    for (int i = 0; i < n; i++) {
        dq.push_back(i + 1);
    }
    
    while (!q.empty()) {
        cal += fun(q.front());
        q.pop();
    }
    cout << cal;
}

✏️ 느낀 점

실버 3이라서 쉽게 생각하고 풀었는데 생각보다 오래 걸렸다. 아무래도 조건들이 많아지면 시간이 좀 더 걸리는 것 같기도 하고 예제4번에서 답이 올바르게 나오지 않는 것을 보고 원인을 알았는데 변수명을 계속 잘못 작성해서(if문에서 pos2를 써야 하는데 pos로 계속 써서 10분동안 못 찾음;;;) 이런 조건문들을 조금 더 빨리 작성할 수 있는 습관도 길러야겠다 → 너무 여유롭게 푸는 것 같음

✏️ 결과