[백준] 1021번 : 회전하는 큐

문제

 

---

풀이

 

입력을 어떻게 처리할지만 구상하면 이 문제는 끝난거나 다름 없다.

이 문제에서 가장 신경써야 하는 것은 각각 다른 위치에 있는 숫자들을 정해진 순서로 뽑아야 하는 것이다.

그니까 입력에서 주어진 수들 말고는 신경 쓸 필요 없고, 입력값들도 그걸 그대로 저장하는 것이 아니라 입력된 위치에 순서 정보로 넣어주면 된다.

 

예제 입력 2에 대해 입력을 처리하면

0

1

0

0

3

0

0

0

2

0

이렇게 된다.

 

1, 2, 3의 순서로 숫자가 뽑히도록 할 것이니 2번, 9번, 5번에 위치한 수들이 순서대로 뽑힐 것이다.

---

소스코드

 

#include <iostream>
#include <deque>

using namespace std;

int left_move(deque<int> dq, int index) {
    int cnt = 0;
    deque<int> tmp = dq;

    while (tmp.front() != index) {
        int num = tmp.front();
        tmp.pop_front();
        tmp.push_back(num);
        cnt++;
    }
    return cnt;
}

void left_pop(deque<int> *dq, int index) { //포인터로 받아야 제대로 수정됨
    while (dq->front() != index) {
        int num = dq->front();
        dq->pop_front();
        dq->push_back(num);
    }
}

void right_pop(deque<int> *dq, int index) { //포인터로 받아야 제대로 수정됨
    while (dq->front() != index) {
        int num = dq->back();
        dq->pop_back();
        dq->push_front(num);
    }
}

int main() {
    deque<int> dq;
    int N, M, l_cnt, r_cnt, tot_cnt = 0;
    int pos[51];

    cin >> N >> M;
    for (int i = 1; i <= M; i++)
        cin >> pos[i];
    for (int i = 1; i <= N; i++) {
        bool isPos = false;
        for (int j = 1; j <= M; j++) { //나올 순서에 따라 해당 위치에 1,2,3...입력
            if (i == pos[j]) {
                dq.push_back(j);
                isPos = true;
            }
        }
        if (!isPos)
            dq.push_back(0);
    }
    for (int i = 1; i <= M; i++) {
        l_cnt = left_move(dq, i); //2번 연산
        r_cnt = dq.size() - l_cnt; //3번 연산(덱 사이즈 - 2번 연산 횟수)
        if (l_cnt < r_cnt) { //2번 연산 실제로 수행
            tot_cnt += l_cnt;
            left_pop(&dq, i);
        } else { //3번 연산 실제로 수행
            tot_cnt += r_cnt;
            right_pop(&dq, i);
        }
        dq.pop_front(); //원소 제거
    }
    cout << tot_cnt << '\n';
}

전체 소스코드다.

 

    deque<int> dq;
    int N, M, l_cnt, r_cnt, tot_cnt = 0;
    int pos[51];

    cin >> N >> M;
    for (int i = 1; i <= M; i++)
        cin >> pos[i];
    for (int i = 1; i <= N; i++) {
        bool isPos = false;
        for (int j = 1; j <= M; j++) { //나올 순서에 따라 해당 위치에 1,2,3...입력
            if (i == pos[j]) {
                dq.push_back(j);
                isPos = true;
            }
        }
        if (!isPos)
            dq.push_back(0);
    }

앞서 풀이에서 말한대로 입력을 받기위해 작성한 코드이다.

 

        l_cnt = left_move(dq, i); //2번 연산
        r_cnt = dq.size() - l_cnt; //3번 연산(덱 사이즈 - 2번 연산 횟수)

특정 수를 빼기 위한 2번 연산과 3번 연산의 횟수를 계산한다.

2번 연산을 위해 left_move라는 함수를 만들었고, 3번 연산을 위한 함수는 만들 필요 없다.

왜냐하면 특정 수에 대한 2번 연산 횟수와 3번 연산 횟수의 합은 덱의 사이즈와 같기 때문이다.

 

int left_move(deque<int> dq, int index) {
    int cnt = 0;
    deque<int> tmp = dq;

    while (tmp.front() != index) {
        int num = tmp.front();
        tmp.pop_front();
        tmp.push_back(num);
        cnt++;
    }
    return cnt;
}

2번 연산의 횟수를 세는 left_move 함수이다. 굳이 설명할 필요는 없을 것 같다.

 

        if (l_cnt < r_cnt) { //2번 연산 실제로 수행
            tot_cnt += l_cnt;
            left_pop(&dq, i);
        } else { //3번 연산 실제로 수행
            tot_cnt += r_cnt;
            right_pop(&dq, i);
        }
        dq.pop_front(); //원소 제거

두 연산 중 더 적게 걸리는 연산을 실제로 수행한다.

 

void left_pop(deque<int> *dq, int index) { //포인터로 받아야 제대로 수정됨
    while (dq->front() != index) {
        int num = dq->front();
        dq->pop_front();
        dq->push_back(num);
    }
}

2번 연산을 실제로 수행하는 left_pop 함수이다. right_pop 함수는 이와 유사하니 굳이 설명하지 않도록 하겠다.