[백준 1021번] 회전하는 큐 (C++, Python 3)

이번 포스트에서는 백준 알고리즘 문제인 회전하는 큐에 대해서 리뷰하겠습니다.

 

solved.ac 기준 실버 3에 위치한 문제입니다.

 

먼저 문제 입니다.

문제에서 N개의 원소를 가지는 양방향 순환 큐와 뽑아내려는 수의 개수 M을 입력받습니다.

다음으로 M개의 뽑아내려는 원소의 인덱스 위치를 입력받습니다.

이때, 원소를 뽑아내기 위해 큐를 왼쪽 혹은 오른쪽으로 이동하는 연산이 몇번 수행되는지 출력하는 문제입니다.

 

큐를 왼쪽, 오른쪽으로 회전하기 위해선, 큐의 앞 혹은 뒤에서 원소를 빼서 반대쪽으로 삽입하는 연산이 필요합니다.

따라서, 이 문제는 덱 자료구조를 활용하여 문제를 해결합니다.

 

해당 문제는 다음과 같은 순서로 풀이합니다.

 

1. 큐의 크기 N과 뽑아내려는 수의 개수 M을 입력 받습니다.
2. 덱에 1~N의 숫자를 삽입합니다. (이때, 큐의 뒷쪽에서 삽입하여 오름차순이 되도록 합니다.)
3. M번 반복하는 반복문에서 다음을 수행합니다.
   1. 뽑아내려는 원소의 인덱스를 입력받아 tmp에 저장합니다.
   2. 덱의 사이즈만큼 반복문을 돌면서 덱에서 tmp값을 찾아 그 인덱스 값을 idx에 저장합니다.
   3. idx값이 덱의 사이즈 / 2 보다 작거나 같다면, tmp값이 덱의 front에 위치할 때 까지 왼쪽으로 회전합니다. 이때, 회전을 1회 실행할 때 마다 cnt 변수에 1씩 더해줍니다.
   4. idx값이 덱의 사이즈 / 2 보다 크다면, tmp값이 덱의 front에 위치할 때 까지 오른쪽으로 회전합니다. 이때, 회전을 1회 실행할 때 마다 cnt 변수에 1씩 더해줍니다.
4. 반복문을 빠져나왔다면 cnt변수를 출력합니다.

Python과 C++ 코드 모두 위와 같은 순서로 진행했습니다. (중간에 변수명은 다를 수 있으나 알고리즘은 동일합니다.)

 

아래는 C++ 코드 입니다.

 

#include <iostream>
#include <deque>
 
using namespace std;
 
deque<int> dq;
 
int main() {
    int idx, tmp;
    int n, m, cnt = 0;
    cin >> n >> m;
 
    for(int i = 1; i <= n; ++i)
        dq.push_back(i);
 
    for(int i = 0; i < m; ++i) {
        cin >> tmp;
 
        for(int k = 0; k < dq.size(); ++k) {
            if(tmp == dq[k]) {
                idx = k;
                break;
            }
        }
 
        if(idx <= dq.size() / 2) {
            while(1) {
                if(tmp == dq.front()) {
                    dq.pop_front();
                    break;
                }
                cnt++;
                dq.push_back(dq.front());
                dq.pop_front();
            }
        }
        else {
            while(1) {
                if(tmp == dq.front()) {
                    dq.pop_front();
                    break;
                }
                cnt++;
                dq.push_front(dq.back());
                dq.pop_back();
            }
        }
    }
    
    cout << cnt << endl;
 
    return 0;
}

 

다음으로 Python 코드입니다.

 

stack = []
def addLast(n) :
    stack.append(n)
 
def addFirst(n) :
    stack.insert(0, n)
 
def removeLast() :
    stack.pop(-1)
 
def removeFirst() :
    stack.pop(0)
 
def front() :
    return stack[0]
 
def back() :
    tmp = len(stack)
    return stack[tmp - 1]
 
n, m = map(int, input().split())
tmp = list(map(int, input().split()))
res = 0
idx = 0
listIdx = 0
 
for i in range(n) :
    addLast(i + 1)
 
while True :
    for i in range(len(stack)) :
        if tmp[listIdx] == stack[i] :
            idx = i
            break
    
    if idx <= len(stack) / 2 :
        while True :
            if front() == tmp[listIdx] :
                removeFirst()
                listIdx += 1
                break
            res += 1
            addLast(front())
            removeFirst()
    else :
        while True :
            if front() == tmp[listIdx] :
                removeFirst()
                listIdx += 1
                break
            res += 1
            addFirst(back())
            removeLast()
    if listIdx == m :
        break
 
print(res)

해당 문제는 일반적인 자료구조를 활용하는 문제로 덱 자료구조에 대해서 이해를 하고 있다면

난이도가 높지는 않은 문제였습니다.

다음 포스트에서는 또 다른 문제로 리뷰하도록 하겠습니다.

 

부족한 내용 읽어주셔서 감사합니다.