[BOJ] 백준 1021 회전하는 큐 간단한설명과 코드 C++

28 Mar 2020

Reading time ~2 minutes

문제 정보

백준 ( 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분
후기 : 좀더 빠르게 파악을 해 보자…

백준 C++시뮬레이션