문제 정보
백준 ( BOJ ) 1021 회전하는 큐
문제 풀이 : 시뮬레이션
문제 출처 : https://www.acmicpc.net/problem/1021
시작 Thinking
특정 숫자를 뺀다고 생각을 해 봅시다.
그렇다면 순서는 어떻게 될까요?
특정 숫자의 바로 뒤가 첫번째 index가 될 겁니다.
이걸 이용해서 풀어주시면 되는데요,
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10 < 3 제거
/ 1 2 3 4 5 6 7
8 9 < 8 제거
/ 1 2
3 4 / 5 6 7 8
앞으로 움직여서 빼든, 뒤로 움직여서 뺴든,
뺀 숫자 바로 뒤가 index 1 부터 시작한다는 점만 생각 하시면 됩니다.
3을 뺀다면, 3바로 뒤인 4부터 1에서 차례대로 증가시키면 끝
뺸 수는, 확인을 위해서 값을 -1로 바꾸어 줍시다.
그다음으로 생각 해야 할 점은,
앞으로 뺼건지, 뒤로 뺄건지 인데요,
해당 값이 몇번째 인덱스인지,
남은 숫자의 갯수가 몇개인지를 고려해서 구해주시면 됩니다.
(size+1) /2 이하면, 앞으로 빼주고
아니라면 뒤로 뺴주면 됩니다.
이동해야 하는 갯수는,
앞으로 이동할 경우, 해당 인덱스 -1 만큼 이동해야하고,
뒤로 이동할 경우에는 (size+1) - 인덱스
만큼 이동시켜 주시면 됩니다.~
코드
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int main() {
int size;
int pick;
int result = 0;
int counter = 0;
cin >> n >> m;
size = n;
vector<int> v(n+1, 0);
for (int i = 0; i < n+1; i++) {
v[i] = i;
}
for (int i = 0; i < m; i++) {
cin >> pick;
if (v[pick] <= (size+1) / 2) {
result += v[pick] - 1;
}
else {
result += size - v[pick] + 1;
}
v[pick] = -1;
counter = 1;
for (int j = pick; j <= n; j++) {
if (v[j] == -1)
continue;
v[j] = counter;
counter++;
}
for (int j = 1; j < pick; j++) {
if (v[j] == -1)
continue;
v[j] = counter;
counter++;
}
size--;
}
cout << result;
return 0;
}
후기
-
소요시간 : 25분
-
후기 : 좀더 빠르게 파악을 해 보자…