[백준/BOJ] 11866번 요세푸스 문제 0 (C/C++)

백준 온라인 저지(BOJ) 11866번 요세푸스 문제 0

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

11866번: 요세푸스 문제 0

* 사용언어 : C언어, C++

 

1. 문제

1번부터 N번까지 N명의 사람이 원을 이루어 앉아있음

1부터 K번째 사람을 한 명 씩 제거하면서 제거되는 순서대로 출력

 

2. 풀이

처음에는 배열로 만들고 제거된 자리에 -1로 표시한뒤 cnt를 늘리며 직접 확인하는 방식을 생각했습니다.

하지만 애초에 매번 K번을 반복하는 것도 비효율적인데 제거된 자리를 계속 skip하면서 세는건 너무 비효율적인 것 같아서

List 구조를 활용하여 자료구조 내에서 제거하는 방식으로 구현해봤습니다.

 

개인적으로 라이브러리 없이 직접 코딩하는걸 선호해서

node 구조체를 선언한 뒤 원형 큐를 Linked List로 구현하여 풀었습니다.

(node의 next를 포인터로 두고 다음 node의 주소로 연결하는 방식)

 

1부터 N까지 node 구조체를 순회하면서 List형태로 연결해주었고,

K번째 숫자 제거는 문제 규칙에 맞게 next를 반복하면서 출력하게 했습니다.

 

시간 효율을 위해 node를 메모리에서 직접 제거하지는 않았고

List의 특성을 활용하여 제거할 node의 이전 node의 연결만 그 다음 node로 변경했습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
11866_요세푸스 문제 0
1128KB	0ms
*/
#include <cstdio>

const int LM = 1001;
int N, K;

struct node {
	int v;
	node* next;
} NODE[LM];

node* cur;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d %d", &N, &K);
	for (int i = 1; i < N; ++i) {
		NODE[i].v = i;
		NODE[i].next = &NODE[i + 1];
	}
	NODE[N].v = N;
	NODE[N].next = &NODE[1];

	cur = &NODE[N];

	printf("<");
	while (cur->next != cur) {
		for (int i = 1; i < K; ++i) cur = cur->next;
		printf("%d, ", cur->next->v);
		cur->next = cur->next->next;
	}
	printf("%d>", cur->v);

	return 0;
}