본문 바로가기

알고리즘 관련/BOJ

BOJ)1021 회전하는 큐

문제: icpc.me/1021


주어진 순서대로 첫번째 원소를 뽑아 원하는 수를 뽑아낼 때 쉬프트 연산의 최소 횟수를 출력하는 문제이다.


쉬프트 연산은 앞 뒤에서 pop push가 가능한 deque을 이용하면 쉽게 해결가능하다 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <algorithm>
#include <deque>
using namespace std;
deque<int> dq;
int n, m, x, r;
int main() {
    scanf("%d%d"&n, &m);
    for (int i = 1; i <= n; i++)
        dq.push_back(i);
    for (int i = 0; i < m; i++) {
        scanf("%d"&x);
        if (dq.front() == x)
            dq.pop_front();
        else {
            int idx = 0;
            for (auto here : dq) {
                if (here == x)
                    break;
                idx++;
            }
            if ((dq.size() / 2< idx) {
                while (dq.front() != x) {
                    int y = dq.back();
                    dq.pop_back();
                    dq.push_front(y);
                    r++;
                }
                dq.pop_front();
            }
            else {
                while (dq.front() != x) {
                    int y = dq.front();
                    dq.pop_front();
                    dq.push_back(y);
                    r++;
                }
                dq.pop_front();
            }
        }
    }
    printf("%d\n", r);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)5582 공통 부분 문자열  (0) 2017.02.08
BOJ)1605 반복 부분문자열  (0) 2017.02.08
BOJ)1893 시저 암호  (0) 2017.02.06
BOJ)9934 완전 이진 트리  (0) 2017.02.06
BOJ)1562 계단 수  (0) 2017.02.06