백준 1021: 회전하는 큐(C언어)

1021번: 회전하는 큐

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다.

N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다.

둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다.

위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

문제풀이

위의 내용을 정리해보면

1. 큐의 크기 N과 뽑아내려는 수의 개수 M을 입력받는다.

2. 뽑으려는 숫자를 M개 입력받는다.

3. 원형 큐라는 가정하에 큐(배열)에서의 현재 위치를 왼쪽 혹은 오른쪽으로 이동한다.

4. 만약 찾고자하는 값과 현재 위치의 값이 같으면 3번을 몇번 수행해줬는지 더해준다.

5. 뽑아내고자 하는 숫자가 다 나올 때까지 3번과 4번을 반복 수행.

 

원형 큐라는 개념을 알고 있다면 문제를 쉽게 해결할 수 있을 것이다.

앞으로 몇번 이동해서 뽑아내고자 하는 값과 뒤로 몇번 이동해서 뽑아내고자 하는 값과 비교를 실행해서 더 낮은 쪽으로

이동해주면 되는데, 뒤로 이동하는 경우는 index = (index + 1) % n을 쉽게 떠올릴 것이다. 

하지만 앞으로 가는 것은 1씩 줄이면 나중엔 음수 값이 나오는 경우가 생길 것이다. 따라서 다른 방법으로 수행해야 한다.

방법은 index = (index + n - 1) % n을 수행하면 되는데 index와 n에 임시로 아무 숫자나 넣고 시행을 해보면 index의 숫자가

1씩 줄어드는 것을 확인할 수 있을 것이다. 이와 같은 방법으로 뽑고자 하는 숫자의 모든 숫자를 뽑을 때까지 반복 수행하면

문제는 해결된다.

세부설명

int n = 입력 n
int m = 입력 m
int fcnt = 앞으로 몇번 이동해야 삭제하고자 하는 인덱스를 찾는지 카운팅
int bcnt = 뒤로 몇번 이동해야 삭제하고자 하는 인덱스를 찾는지
int temp = index의 위치를 임시로 담아 사용할 변수
int ans = 정답을 카운팅 해주는 변수
int index = 현재 큐에서의 인덱스 위치 (a배열에 사용)
int search = 찾고자 하는 인덱스 위치 (b배열에 사용)
int a[50] = n개의 큐 초기화
int b[50] = m개의 값 입력

최종코드

#include<stdio.h>

int main() {
	int n, m, fcnt, bcnt, temp, ans = 0, index = 0, search = 0;
	int a[50] = { 0 };
	int b[50] = { 0 };

	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		scanf("%d", &b[i]);
		b[i]--;
	}
	for (int i = 0; i < n; i++) {
		a[i] = 1;
	}
	while (search < m) {
		if (a[index]) {
			if (index == b[search]) {
				a[index] = 0;
				index = (index + 1) % n;
				search++;
			}
			else {
				fcnt = 0, bcnt = 0, temp = index;
				while (temp != b[search]) {
					temp = (temp + n - 1) % n;
					fcnt += a[temp];
				}
				temp = index;
				while (temp != b[search]) {
					temp = (temp + 1) % n;
					bcnt += a[temp];
				}
				if (fcnt <= bcnt) ans += fcnt;
				else ans += bcnt;
				index = (b[search] + 1) % n;
				a[b[search]] = 0;
				search++;
			}
		}
		else {
			while (!a[index]) {
				index = (index + 1) % n;
			}
		}
	}
	printf("%d", ans);
}