[백준/C & C++] 1158 요세푸스 문제

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

C

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

int main()
{
	int n, k, i, index;
	scanf("%d %d", &n, &k);

	if (k == 1)
	{
		printf("<");
		for (int i = 0; i < n-1; i++) printf("%d, ", i + 1);
		printf("%d>", n);
		return 0;
	}

	int* arr = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) arr[i] = 0;

	printf("<");
	for (i = 0, index = k - 1; index < n; index += k, i++)
	{
		arr[index] = i + 1;
		printf("%d, ", index + 1);
	}
	index -= k;

	for (; i < n; i++)
	{
		int cnt = 0;
		while (cnt < k)
		{
			index = (index < n - 1) ? index + 1 : 0;
			if (arr[index] == 0)cnt++;
			if (cnt == k)
			{
				arr[index] = i + 1;
				if (i < n - 1) printf("%d, ", index + 1);
				else printf("%d>", index + 1);
				break;
			}
		}
	}
	free(arr);
	return 0;
}

C++

#include <iostream>
#include <cstdlib>
using namespace std;

int main()
{
	int n, k, i, index;
	cin >> n >> k;

	if (k == 1)
	{
		cout << "<";
		for (int i = 0; i < n - 1; i++) cout << i+1 << ", ";
		cout << n << ">";
		return 0;
	}

	int * arr = new int[n];
	for (int i = 0; i < n; i++) arr[i] = 0;

	cout << "<";
	for (i = 0, index=k-1; index < n; index += k, i++)
	{
		arr[index] = i + 1;
		cout << index+1 <<", ";
	}

	index -= k;
	for (; i < n; i++)
	{
		int cnt = 0;
		while (cnt < k)
		{
			index = (index < n - 1) ? index + 1 : 0;
			if (arr[index] == 0) cnt++;
			if (cnt == k)
			{
				arr[index] = i + 1;
				if (i < n - 1) cout << index + 1 << ", ";
				else cout << index + 1 << ">";
				break;
			}
		}
	}

	delete[]arr;
	return 0;
}

코드 설명

n, k를 입력받고 k가 1인 경우에는 1~n까지를 출력 요건에 맞춰 출력하고 프로그램을 종료한다. 

k가 1이 아닌 경우에는 원소가 n개인 동적배열을 만들고 값을 모두 0으로 초기화한다. 

index는 k-1부터, i는 0부터 시작해서 index가 n보다 작을 때까지 index+=3, i++를 하면서 반복문을 돈다. 이 반복문에서는 k의 배수-1 인덱스에 저장된 k의 배수가 출력된다. (주어진 예제에서는 3,6을 출력하는 부분이다. ) 반복문이 종료되면 index -=k를 해서 반복문에서 마지막으로 출력한 값의 인덱스를 저장하고 있도록 한다.

 

두 번째 반복문은 다시 앞쪽으로 돌아와서 출력하지 않은 수를 출력하는 부분이다. 반복문을 두 개로 나눈 이유는 k의 배수를 출력할 때는 고려할 것이 전혀 없지만 k의 배수가 아닌 값은 앞에서의 출력으로 인해 출력되는 값들의 간격이 일정하지  않기 때문이다. (주어진 예제에서 2,7,5,1,4에 해당한다.) 그래서 k의 배수가 아닌 값들은 직접 개수를 세어 가며 출력했다. index를 1씩 증가시키는데 index가 n-1이면 배열의 마지막이기 때문에 0으로 바꿔준다. 해당 인덱스에 저장된 값이 0이면 출력된 적이 없는 값이다. 따라서 cnt를 증가시켜준다. cnt가 k이면 현재 출력할 값을 만난 것이다. 출력했음을 arr[index] = i+1로 표시해주고, 출력 조건에 맞춰 출력한다.  

 

동적배열을 해제하고 프로그램을 종료한다. 

 

느낀 점

2달 전에 처음 c로 도전했다가 시간초과가 나와서 고민이 많았던 문제이다. 바로 기말고사 준비를 하느라 한동안 백준을 풀지 못했고 오늘 가벼운 문제들을 풀다가 다시 도전했다. 

 

시간초과가 나온 코드의 경우에는 메인함수 내에 동적할당으로 배열을 만들고 void pop(int arr[]) 함수를 따로 만들었다. 

void pop(int arr[])
{
	if (n == 0) return;
	for (int j = 0; j < k; j++)
	{
		int start = arr[0];
		for (int i = 0; i < n - 1; i++) arr[i] = arr[i + 1];
		arr[n - 1] = start;
	}
	printf("%d", arr[n - 1]);
	n--;
}

위의 코드가 pop 함수였다. k번 배열의 원소를 앞당겨서(이때 arr[0]은 arr[n-1]에 저장했다.) arr[n-1]에 저장되어 있는 값을 출력하고 n--을 해서 pop을 하도록 코드를 작성했다. n이 0이면 배열의 모든 값을 출력했으니 함수를 종료한다.  시간초과의 원인이 이 부분이라고 생각해서 pop을 하지 않고 문제를 풀 수 있는 방법을 찾아야 했다.

 

그러다가 구조체를 쓰면 될 것 같아서 구조체를 원소를 갖는 배열을 만들었다. 구조체에는 int num(==출력될 값), check(==출력 여부를 표시하는 용)을 원소로 했다. 그렇게 해서 pop을 하지 않고 코드를 작성했는데 제시된 예제뿐만 아니라 내가 시험해본 값들이 돼서 제출했었다. 맞는 줄 알았는데 채점 퍼센트가 거의 끝나갈 때 쯤 틀렸다고 떴다. 그때 내가 k=1일 때를 테스트해보지 않은 게 떠올라서 바로 확인해보니 여기에서 출력 양식이 맞지 않았다. 바로 k=1인 경우를 고려하는 코드를 추가해보니 바로 통과했다!

 

c로 코드를 쓰다가 내가 구조체에서 num에 해당하는 값을 사용하지 않았다는 걸 알았다. index+1로 충분히 대체할 수 있는 값이라서 c는 구조체를 만들지 않았고,  check를 저장할 int배열을 만들어서 풀었다. 그리고 c++도 구조체를 없애고 int배열로만 다시 풀었다. 

 

가볍게 봤던 문제였는데 "맞았습니다!"를 보기까지 돌고 돌아서 시간이 오래 걸렸다. c++의 경우에는 queue 헤더파일을 사용하면 코드를 더 간결하게 쓸 수 있는 것을 후에 알았다. 공부를 더 많이 해야 할 것 같다.