[백준-1021] 회전하는 큐

1021번: 회전하는 큐

 

단순한 구현문제이다.

시간제한은 2초임에 불구하고 입력값의 크기가 50이므로 n^2 의 복잡도를 가질 시 2500 밖에 걸리지 않아 매우 널널한 문제이다.

index 를 가지고 0일때 왼쪽으로 돌리면 다시 오른쪽 끝으로, 반대로 n일 때 오른쪽으로 돌리면 0으로.. 의 로직을 기준으로 코드를 짜면 끝나는 코드이다.

밑의 코드는 단순 무지성으로 코드만 짠거긴 한데 중간중간 왼쪽으로 돌릴지, 오른쪽으로 돌릴지에 대해 그리디 방식으로 구하게 되면 코드가 더 깔끔하게 나오게 된다.

 

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <algorithm>


using namespace std;

int num[100];
int check[100];
int arr[100];
int n, m;

int get_right_num(int a) {
	return (a >= n) ? 1 : a + 1;
}
int get_left_num(int a) {
	return (a == 1) ? n : a - 1;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) num[i] = i;
	for (int i = 1; i <= m; i++) cin >> arr[i];
	
	int idx = 1;
	int res = 0, left_idx, right_idx, left_cnt, right_cnt;
	for (int i = 1; i <= m; i++) {
		left_idx = idx, left_cnt = 0;
		right_idx = idx, right_cnt = 0;

		while (num[left_idx] != arr[i]) {
			left_idx = get_left_num(left_idx);
			if (check[left_idx] == 0) left_cnt += 1;
		}

		while (num[right_idx] != arr[i]) {
			right_idx = get_right_num(right_idx);
			if (check[right_idx] == 0) right_cnt += 1;
		}
		
		idx = get_right_num(right_idx);
		while (check[idx] != 0) {
			idx = get_right_num(idx);
		}
		check[right_idx] = 1;
		res += min(left_cnt, right_cnt);
	}
	cout << res;
	return 0;
}