JArchive 프로그래밍 일기

문제

회전하는 큐 백준 1021

"맞았습니다" 코드

#include <bits/stdc++.h>
using namespace std;
​
int n, m; // 큐의 크기, 뽑아내려는 개수.
int target;
deque<int> de;
int cnt = 0;
​
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.ignore(0);
​
    cin >> n >> m;
​
    for(int i = 1; i <= n; i++){
        de.push_back(i); // 1 부터 n까지 숫자 넣기
    }
​
    for(int i = 0; i < m; i++){ // 찾기 시작
​
        cin >> target;
​
        // 타겟의 인덱스를 찾아낸다.
        int targetIdx = 0;
        for(int i = 0; i < de.size(); i++){
            if(de[i] == target){
                targetIdx = i;
                break;
            }
        }
​
        if(targetIdx > de.size()-targetIdx){
            while(1){
                if(de.front() == target) {
                    de.pop_front();
                    break;
                }
                de.push_front(de.back());
                de.pop_back();
                cnt++;
            }
        }
        else{
            while(1){
                if(de.front() == target) {
                    de.pop_front();
                    break;
                }
                de.push_back(de.front());
                de.pop_front();
                cnt++;
            }
        }
    } // for
​
    cout << cnt;
    return 0;
}

리뷰

문제를 주의 깊게 안읽어서 고생했다.

일단 타겟이 deque에서 몇 번째 인덱스인지 찾아내는 것이 중요하다. 

그러면, 2번 연산을 연속 해서 뽑아내는게 빠른지 3번 연산을 해서 뽑아내는게 빠른지 판단할 수 있다.

1번 연산은 pop_front()이다.
2번 연산은 front()를 push_back()하고, pop_front() 한다.
3번 연산은 back()을 push_front()하고, pop_back() 한다.

돌리다가 front()가 뽑아낼 타겟이라면 1번 연산 pop_front() 하고 break 하면 된다.

원소를 뽑아내는게 반드시 front()와 비교해서 pop_front() 해야하는데.

오른쪽으로 돌리다가 pop_back()하는 바람에 계속 틀리게 풀고 있었다.

다시 풀어봐야 할 문제.