[백준 1158, 20301] 요세푸스, 반전 요세푸스 (C++)

 백준 1158번 (요세푸스 문제)

문제 출처

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

1158번: 요세푸스 문제

문제 

문제 접근 방식

요세푸스 문제는 queue를 이용하였다.

 

N명의 사람이 원을 이루며 앉아있는 상황으로 주어지는데, 원으로 생각하는 것보다 queue를 이용하기 위해 일렬로 나열되어 있는 상황으로 생각하는 것이 더욱 접근하기 쉽다.

 

또한, K번째 사람을 제거하는 방식은, 맨 처음 사람부터 K - 1번째 사람을 맨 뒤로 보내주면 기존에 K번째에 있던 사람이 가장 처음 위치에 오게 되고, 즉 queue의 가장 첫번째 원소가 되기 때문에, pop을 해주면 된다.

 

출력 예시에 주어진 < > 와 , 는 출력 시 적절한 조건문을 통해 구현할 수 있다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
using namespace std;


int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int N, K;
	cin >> N >> K;
	queue<int> q;
	for (int i = 0; i < N; i++)
		q.push(i + 1);
	cout << '<';
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < K - 1; j++) {
			q.push(q.front());
			q.pop();
		}
		if (i != N - 1) {
			cout << q.front() << ',' << ' ';
			q.pop();
		}
		else
			cout << q.front() << '>';
		
	}
	return 0;
}

느낀 점

일단, 이 문제를 처음 접했을 때 queue를 이용하면 편리하다는 사실을 알아차리는 것은 어렵지 않았다.

그런데, 기존에 내가 쓰던 C를 통해 구현하면 코드가 굉장히 복잡하고 길어질 것 같았다.

(왜냐하면, C로 queue를 구현하는 과정은 꽤나 복잡하기 때문이다.)

그러나, 최근에 C++을 공부하고 이용하면서 C++에서는 queue를 정말 간단하게 구현하고 사용할 수 있음을 알게 되었다.

정말로 C++을 이용하여 문제를 풀었더니 정말 간단하게 코드를 구현할 수 있었다.

C로 다시 풀어보라고 하면 풀 엄두가 안 난다...ㅎ

 

백준 20301번 (반전 요세푸스)

문제 출처

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

20301번: 반전 요세푸스

문제

문제 접근 방식

앞서 리뷰한 '요세푸스 문제' 와 굉장히 유사하다.

기존의 요세푸스 문제에 M을 추가적으로 입력받아 이에 대한 새로운 조건이 추가되었을 뿐이다.

 

M명의 사람이 제거될 때마다 원을 돌리는 방향을 계속 바꾼다는 조건이 추가되었다.

처음에는, 사람 한 명을 제거할 때마다 cnt를 1씩 증가시켜 cnt가 M과 같아지면 방향을 바꿔주고, cnt는 다시 0으로 초기화해주는 방식으로 반복문을 구현하면 되겠다고 생각했다.

 

기존 요세푸스 문제처럼 queue를 이용하려고 했으나, 문제점이 있었다.

queue는 front에서 pop을 하고, rear(back)에서 push를 해주는 특징이 있다.

그런데, 만약에 M명의 사람을 제거하게 되어 방향을 바꿔주게 되면, rear(back)에서 pop을 해주고 front에 push를 해주어야 하는 상황이 된다. 

하지만, queue의 rear(back)에서 pop을 하거나 front에서 push를 해주는 기능은 없다.

 

여기서, 새로운 자료구조인 deque를 이용하기로 했다.

deque는 front에서 push도 할 수 있고, pop도 할 수 있다.

또한, back에서 push도 할 수 있고, pop도 할 수 있다.

즉, 내가 필요로 했던 기능을 가지고 있는 자료구조인 것이다.

 

push와 pop을 해주는 구간은 구현이 어렵지 않았다.

다만, 까다로웠던 점은 M명이 제거될 때마다 방향이 바뀌는 점이었다.

방향이 바뀐다는 정보를 저장할 변수 flag를 선언하였고, 처음에 0으로 초기화해주었다.

방향이 바뀌면 flag가 1이 되고, 다시 방향이 바뀌면 flag가 0이 되고, 이 과정이 반복되도록 구현해야 했다.

 

이 방향이 바뀌는 시점은 cnt가 m과 같아질 때이므로 if (cnt == m) 이라는 조건문을 작성하였다.

또한, 이 조건문 내부에서, flag = 1 - flag 라는 구문을 작성해주어 조건문의 조건을 만족할 때마다 flag가 0이었다면 1이 되고, 1이었다면 0이 되도록 구현해주었다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <deque>
using namespace std;


int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, k, m;
	int cnt = 0;
	int flag = 0;;
	cin >> n >> k >> m;
	deque <int> dq;
	for (int i = 0; i < n; i++)
		dq.push_back(i + 1);
	for (int i = 0; i < n; i++) {
		if (flag == 0) {
			for (int j = 0; j < k - 1; j++) {
				dq.push_back(dq.front());
				dq.pop_front();
			}
			cout << dq.front() << '\n';
			dq.pop_front();
			cnt++;
		}
		else {
			for (int j = 0; j < k - 1; j++) {
				dq.push_front(dq.back());
				dq.pop_back();
			}
			cout << dq.back() << '\n';
			dq.pop_back();
			cnt++;
		}
		if (cnt == m) {
			flag = 1 - flag;
			cnt = 0;
		}
	}
	return 0;
}

느낀 점

deque를 처음 사용해보았다.

C에서는 접하지 못했던 개념이기 때문에 어렵지 않을까 생각했는데, 이용하기가 매우 쉬웠다.

stack, queue, deque에 관한 문제를 많이 풀어보면서 어느 상황에서 어느 자료구조를 사용해야 할지에 대한 직관을 키워야겠다는 생각을 하게 되었다.