아이템먹기, 원형 큐 사용하기 훈련

문제

아이템을 먹어주는 프로그램을 만들려고 한다. 단, 아이템을 먹는 규칙이 있다. 바닥에 떨어져 있는 아이템을 1번 부터 N번까지 있을때, S번의 아이템부터 시작하여 M번째 아이템을 먹는다. 그 후 다음 번호의 아이템부터 셈하여 M번째 아이템을 먹게 된다. 아이템을 먹게되는 순서를 구하라.

예를들어 아래와 같다고 하자.

S가 1이고 M이 4이므로 가장 먼저 먹을 수 있는 아이템은 4이다. 이후 4 다음인 5부터 M번째 아이템은 1이므로 두번째 먹을 수 있는 아이템은 1이다. 

 

다음으로 먹게 될 아이템은 1이다. 이와 같은 순서로 다음은 6, 5, 7, 3, 2의 순서로 아이템을 먹게 된다.

 

입력

N개의 아이템이 입력되며 N은 1부터 10000개이다. 시작하는 아이템 번호가 S로 입력되며 S는 1부터 N까지 이다.

M이 입력되며 M은 1부터 N-1까지이다.

N, S, M의 값이 차례로 입력된다.

7 1 4

 

출력

아이템을 먹게되는 순서가 출력된다.

4 1 6 5 7 3 2 

 

---

문제해결

단순하게 check배열을 만들어서 모든 순차를 다 돌아보는 방법도 있으나 이는 timeout이 발생하게 된다. 따라서 Queue를 활용해야한다.

1) N개의 아이템, S번째부터 Enque시킨다.

2) M번째까지 Deque하면서 Que의 끝에 Enque 시킨다.

3) M번째의 아이템은 Deque하여 item을 먹은 것으로 처리한다.

 

단, Linear queue로는 case가 너무 크기 때문에 공간복잡도를 초과한다. 따라서 Circular queue를 활용해야 한다.

 

Circular Queue
Circular Queue는 선형 배열을 원형이라고 가정하여 사용하는 논리적 개념이다. que의 Write와 Read 포인터가 배열의 크기를 초과하면 다시 첫 배열인 0번 배열로 이동 시켜 queue작업을 진행하게 된다.

그림과 같이 되는 것이다. 여기서 문제점이 하나 있는데 Circular queue에서는 Empty que와 Full que를 기존대로 는 구분하기가 어렵다. 따라서 wp와 rp가 같을때를 Empty que로 정의한다.
반면 Full que는 아래처럼 (wp+1)%N = rp 일때로 정의하게 된다.
논리적으로 que의 맨 마지막 배열은 비워두게 된다.

#include <stdio.h>

int N;
int S;
int M;
int check[10000+10];
int myque[10000+10];
int rp, wp;

void Enque(int x){
	myque[wp] = x;
	wp = (wp+1) % N;
}

int Deque(){
	int data = myque[rp];
	rp = (rp + 1) % N;
	return data;
}

void Input(){
	scanf("%d %d %d", &N, &S, &M);
}

void Solve2(){
	//초기화
	int chk = 0; //명수 체크
	int cnt = 0; //반복 수
	rp=0; wp=0;
	int k = S-1; //시작 위치
	for(int i=0; i<N; i++){
		Enque(k);
		k= (k+1)%N;
	}
	
	//반복
	int data;
	while(chk<N)
	{
		for(cnt=1; cnt<=M; cnt++) //deque해서 Enque
		{
			if(cnt==M)
			{
				data = Deque();
				printf("%d ",data+1);
				chk++;
				break;
			}
			data = Deque();
			Enque(data);
		}
		
	}
}

/*
void Solve(){
	int i;
	int j;
	int k = S-1; //시작
	int cnt;
	for(i=0; i<N; i++){
		for(cnt=0; ; k=(k+1)%N){
			if(check[k] == 1) continue;
			cnt++;
			if(cnt==M) break;
		}
		check[k]=1;
		printf("%d ", k+1);
	}
}
*/

int main() {
	Input();
	//Solve();
	Solve2();
	
	return 0;
}