[C] 백준 | 11866번 코드 - 요세푸스 문제 0

>문제

> 핵심

큐 or 배열

>풀이과정

일단 N, K 값을 입력받고, 크기 N만큼의 배열을 동적할당한다.

그 이후에 배열에 1부터 N까지의 값을 차례대로 집어넣는다.

 

이제 하나씩 값을 제거할텐데, 출력 조건을 보면 <3, 6, 2, 7, 5, 1, 4> 처럼 괄호 처리를 따로 해줘야한다.

그래서 "<%d" + ", %d" + ">" 세부분으로 나눠 출력하기 위해서 첫번째 값 삭제는 반복문 밖에서 먼저 해줬다.

 

배열에는 양의 정수가 채워져있기 때문에 제거된 값은 -1로 채워넣는 것으로 했다.

K번째 값을 삭제하는거니까 배열에서는 먼저 table[K-1]번째 값을 지워준다

 

그 이후에 인덱스 [K-1]번부터 시작해서 반복문을 돈다.

j=0부터 올라가면서 table[(idx+j) % N] != -1 양의정수를 만날때마다 cnt++ 해주고, cnt가 K와 같아지면 탈출.

 

여기서 (idx+j) % N을 하는 이유는 원형으로 돌아야하기 때문. 

4칸짜리 배열을 돈다면 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, ... 이렇게 돌기 위해서

 

아무튼 그래서 또 K번째 값을 찾으면 인덱스를 현재 위치로 갱신해주고 현 위치는 -1 값을 넣고 다시 반복하는 과정을 거치는게 이 코드의 전부다.

 

어째 말로 풀어쓰는게 더 어렵다..

 

그리고 문제를 풀고나서 다른사람들의 코드를 보니 큐로 푼 사람들도 많았다.

 

배열에서 3번째 값을 삭제한다고 하면, 

1. pop -> push (꼭대기에 있는 값을 바닥에 넣음)

2. pop -> push

3. pop 해서 출력.

4. 위 과정을 큐가 비기 전까지 반복,

 

구조가 굉장히 단순해진다

역시 하나의 문제를 푸는데도 굉장히 다양한 방법이 있다.

최적의 알고리즘을 찾고 설계하는게 코딩을 하는 사람의 목표가 아닐까 싶다.

 

일단 그러려면 많은 문제를 접해보고 풀어봐야 할 것 같다. 

백준 골드는 달고 다시 생각해보자. 으쌰!

>깨달은점

문제 맞았다고 그냥 치우지 말고 다른사람들 코드도 비교해봐서 어떤게 더 효율적인 방법인지 한번쯤은 생각해보자

>코드

1. 배열로 해결

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main()
{
	int i, j, N, K, cnt, idx;

	scanf("%d %d", &N, &K);

	int* table = (int*)calloc(N, sizeof(int));

	for (i = 0; i < N; i++) /*값 채워넣기*/
	{
		table[i] = i + 1;
	}

	printf("<%d", table[K - 1]); /*첫번째 제거 처리*/
	table[K - 1] = -1;

	for (i = 0, idx = K; i < N - 1; i++) /*두번째 제거부터 시작*/
	{
		cnt = 0; j = -1;
		while (cnt < K) /* 값이 존재하는 배열을 K번 지날때까지 j += 1 */
		{
			j += 1;
			if (table[(idx + j) % N] != -1)
				cnt += 1;
		}
		idx = (idx + j) % N; /*인덱스 갱신*/
		printf(", %d", table[idx]);
		table[idx] = -1;
	}
	printf(">");
	return 0;
}

 

2. 큐로 해결

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define SIZE 1001

typedef struct {
	int queue[SIZE];
	int front, rear;
}QueueType;

void init_queue(QueueType* q)
{
	q->front = q->rear = 0;
}

int is_full(QueueType* q)
{
	return ((q->rear + 1) % SIZE == q->front);
}

int is_empty(QueueType* q)
{
	return (q->front == q->rear);
}

void push(QueueType* q, int e)
{
	if (is_full(q))
		return;

	q->rear = (q->rear + 1) % SIZE;
	q->queue[q->rear] = e;
}

int pop(QueueType* q)
{
	if (is_empty(q))
		return -1;

	q->front = (q->front + 1) % SIZE;
	return q->queue[q->front];
}

int size(QueueType* q)
{
	if (q->front < q->rear)
		return q->rear - q->front;
	else
		return SIZE - q->front + q->rear;
}

int main()
{
	QueueType Q; init_queue(&Q);

	int i, j, N, K, tmp;

	scanf("%d %d", &N, &K);

	for (i = 0; i < N; i++)
	{
		push(&Q, i + 1);
	}

	printf("<");
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < K - 1; j++)
		{
			tmp = pop(&Q);
			push(&Q, tmp);
		}
		if (size(&Q) == 1)
			break;
		tmp = pop(&Q);
		printf("%d, ", tmp);
	}
	printf("%d>", pop(&Q));

	return 0;
}