반응형
Notice
Recent Posts
Recent Comments
Link
«   2024/12   »
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
Archives
Today
Total
관리 메뉴

코딩하기 좋은날

백준 1021회전하는 큐 본문

백준(Baekjoon) 문제

백준 1021회전하는 큐

huiung 2019. 2. 19. 13:26
반응형

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 deque 구조를 이용하여 초기에 원소의 위치를 입력받고 그 원소를 맨 앞으로 위치시켜 뽑아 내는데 push를 몇번 해야 하는지 최소 횟수를 구하는 문제입니다. 

 

저는 이 문제를 우선 순서대로 찾아야 하는 위치의 원소의 현재 위치를 찾은뒤 그 위치가 전체 덱의 사이즈의 1/2 보다 크다면 뒤에서 앞으로 보내고 그렇지 않다면 앞에서 뒤로 보내도록 코드를 작성하였습니다. 해당 위치의 원소를 가장 앞으로 보내기 위해서는 앞의 원소들을 뒤로 보내거나 뒤의 원소들을 앞으로 보내야 하는데 이때 최소 횟수가 되기 위해서는 전체 덱의 사이즈 1/2을 기준으로 판별을 하여야 합니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <deque> 

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	deque<int> dq;
	int N,M;
	int arr[50] = {0, };
	cin >> N >> M;
	 
	for(int i = 1; i <= N; i++)
		dq.push_back(i);
	
	for(int i = 0; i < M; i++) {
		cin >> arr[i];
	}
	
	int n = 0;
	int num = 0;
	while(n < M) {
		int index;
		for(int i = 0; i < N; i++) {
			if(dq[i] == arr[n]) {
				index = i;
				break;
			}
		}
		
		while(1) {
			
			if(dq.front() == arr[n]) {
				dq.pop_front();
				n++;
				break;
			}
			
			if(index>dq.size()/2) {
				int x = dq.back();
				dq.pop_back();
				dq.push_front(x);
				num++;
			}
			else {
				int x = dq.front();
				dq.pop_front();
				dq.push_back(x);
				num++;
			}
	
		}
		
	}
	cout << num;
	return 0;
}

 

반응형

'백준(Baekjoon) 문제' 카테고리의 다른 글

백준 1676 팩토리얼 0의 개수  (0) 2019.02.21
백준 1003 피보나치 함수  (0) 2019.02.21
백준 5430 AC  (0) 2019.02.19
백준 1916 최소비용 구하기  (0) 2019.02.18
백준 16568 엔비스카의 영혼  (0) 2019.02.18