문제 링크 : https://www.acmicpc.net/problem/1966
해결방법 :
- 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
- 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.
문제의 조건 그대로 알고리즘을 설계하면 답을 구할 수 있다.
맨앞에 요소보다 뒤에 큰값이 없다면 그대로 queue에서 제거하면서 빼낸다.
아니라면 queue에서 맨앞에 요소를 뒤로 옮겨준다.
이걸 구현하기 위해서 앞에 추가삭제, 뒤에 추가삭제가 용이한 STL의 dequeue 자료구조를 사용했다.
그리고 찾고자 하는 문서정보를 가지고 있어야하기에 pair도 사용하였다. (second 요소 : 원래 주어진 인덱스위치)
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 | #include<iostream> #include<queue> using namespace std; deque < pair<int, int>> dq; int main() { int t; cin >> t; for (int te = 0; te < t; te++) { int N; int M; int flag; int check; int find; int size = 0; int cnt = 0; int num; scanf("%d %d", &N, &M); for (int i = 0; i < N; i++) { scanf("%d", &num); dq.push_back(make_pair(num, i)); } while (!dq.empty()) { flag = 0; check = dq.front().first; find = dq.front().second; size = dq.size(); for (int i = 1; i < size; i++) { if (check < dq[i].first) { flag = 1; break; } } if (!flag) { dq.pop_front(); cnt++; if (find == M) { printf("%d\n", cnt); break; } } else { dq.push_back(dq.front()); dq.pop_front(); } } while (!dq.empty()) { dq.pop_front(); } } } | cs |
반응형
'PS > 백준' 카테고리의 다른 글
| 1110번 더하기 사이클 (0) | 2018.11.14 |
|---|---|
| 2448번 별 찍기 - 11 (0) | 2018.11.12 |
| 7576번 토마토 (0) | 2018.10.24 |
| 2839 설탕배달 (0) | 2018.10.19 |
| 14891번 톱니바퀴 (0) | 2018.10.15 |