백준 1158번: 요세푸스 문제 풀어보기 (C++)🤓

실버4 짜리 문제

문제 링크: https://www.acmicpc.net/problem/1158

 

문제 페이지

 

이 문제는 배열이나 벡터, 큐 등등 여러가지로 풀 수 있지만 가장 효율적인 큐로 한번 풀어보았습니다.

왜 큐가 가장 효율적인지는 코드에서 설명하겠습니다.

 

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

int main()
{
	int n, k;

	cin >> n >> k;

	queue<int> que;
	int length = 0;
	
	for (int i = 1; i < n+1; ++i)
	{
		que.push(i); //숫자들 채워주기 (큐는 FIFO방식이기 때문에 그냥 이렇게 반복문 돌려도 됨)
	}

	length = que.size();
	cout << "<";
	for (int i = 0; i < length; ++i)
	{
		for (int j = 0; j < k - 1; ++j)
		{
			int q = que.front(); //pop으로 제거하기 전에 임의의 변수에 front값 넣어두기
			que.pop(); //pop으로 제거하고
			que.push(q); //front에 있던 값을 뒤로 보내서 넣어주기
		}
		if (i == length - 1) //마지막에는 , 를 안 붙이고 홑화살표만 붙어야하기 때문에 예외처리
			cout << que.front();
		else // , 붙어주기
			cout << que.front() << ", ";
		que.pop(); //한명 제거
	}
	cout << ">";
}

 

우선 요세푸스 문제를 몇번째 사람을 제거할지 고를 때 그만큼 앞에 사람을 뒤로 옮기면 된다는걸 알 수 있는데.

이는 큐의 원리 속에서 특히 원형큐에 원리와 일치한데,

여기서 다른 자료형보다 더 효율적인 이유가 나온다.

 

배열을 예시로 들자면 몇번째 사람을 인덱스로 딱 고르고 제거하면 빈 공간이 생겨 다른 데이터들을 옮겨 채워줘야합니다.

이때 다른 데이터를 옮기는 로직이 들어가 삭제한번에 O(N)시간이 소요되기 때문에 시간복잡도 상 O(N^2)이라는 시간복잡도를 가지게된다.

하지만 큐는 pop이나 push를 할시 특성상 알아서 데이터가 옮겨지고 데이터 제거 후 삽입이 이뤄지지않기 때문에 시간복잡도가 O(N x K)를 가져 효율적입니다.

 

요세푸스 문제 풀이였습니다.