Contents
문제
문제를 보시려면 링크를 클릭해주세요.
풀이
STL deque를 사용하여 풀었습니다.
- 뽑으려는 수의 위치가 왼쪽, 오른쪽 중 어느 방향과 더 가까운지를 판별합니다.
- 왼쪽, 오른쪽 중 이동 횟수가 적은 방향으로 push, pop을 실행합니다.
left ＞ right조건의 경우는 push, pop 횟수보다 이동횟수가 +1이므로 cnt++ 를 한 번 더 해줍니다.- 총 이동 횟수의 합을 출력합니다.
소스 코드
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <deque>
using namespace std;
int main(int argc, char**argv) {
ios::sync_with_stdio(0);
cin.tie(0);
deque<int> DQ;
int N, M;
int left, right;
int cnt = 0;
cin >> N >> M;
for(int i=1; i<=N; i++){
DQ.push_back(i);
}
while(M--){
int num;
cin >> num;
for(int i=0; i<DQ.size(); i++){
if(DQ[i] == num){
left = i;
right = DQ.size()-i;
break;
}
}
if(left<=right){
while(1){
if(DQ.front()==num)
break;
DQ.push_back(DQ.front());
DQ.pop_front();
cnt++;
}
DQ.pop_front();
}
else{
cnt++;
while(1){
if(DQ.back()==num)
break;
DQ.push_front(DQ.back());
DQ.pop_back();
cnt++;
}
DQ.pop_back();
}
}
cout << cnt;
return 0;
}