기타:: 230105 일기

백준 풀이 - 덱 연습문제

문제리뷰

1021 회전하는 큐

처음에는 맨 처음 큐의 인덱스에서 양 끝의 원소와의 차이를 더해 최종값을 구하려고 했으나

회전하는 큐이기 때문에 인덱스의 변화가 있어 인덱스를 하나하나 건드는 방식으로 구했다.

인덱스를 하나하나 건드는 과정에서 초기값은 건들면 안 돼서

move와 같이 얼마나 움직였는지 구하는 변수나 현재 인덱스를 나타내는 배열을 선언해서 구했다.

인덱스를 하나한 건드는 과정에서 큐에서 숫자가 빠질 때 1을 안 빼서 헤맸다..

 

또한 정답 코드를 보니 STL 함수 중에 find 함수를 통해 변한 인덱스를 쉽게 구할 수 있었다.!

 

1021 회전하는 큐

#include <bits/stdc++.h>
using namespace std;

int n, m;
int idx[50];
int curidx[50];
deque<int> DQ;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for(int i = 0; i < m; i++)
		cin >> idx[i];
	copy(begin(idx), idx+m, begin(curidx));
	
	for(int i = 1; i <= n; i++) {
		DQ.push_back(i);
	}
	
	int index = 0, sum = 0;
	while(index < m) {
		if(DQ.front() == idx[index]) {
			DQ.pop_front();
			index++;
			for(int i = index; i < m; i++) {
				curidx[i]--;
			}
			continue;
		}
		
		if(curidx[index] <= DQ.size()/2+1){
			int temp = DQ.front();
			DQ.pop_front();
			DQ.push_back(temp);
			for(int i = index; i < m; i++) {
				curidx[i]--;
				if(curidx[i] <= 0) curidx[i] += DQ.size();
			}
		}
		else {
			int temp = DQ.back();
			DQ.pop_back();
			DQ.push_front(temp);
			for(int i = index; i < m; i++) {
				curidx[i]++;
				if(curidx[i] > DQ.size()) curidx[i] %= DQ.size();
			}
		}
		sum++;
	}
	cout << sum;
	
	return 0;
}