1158번: 요세푸스 문제

Memo

로직 설명

• Queue 자료구조의 특징(FIFO)을 이용하여, K - 1 횟수 만큼 pop과 push를 연속해서 진행하고, 그 후 큐 맨 윗부분에 존재하는 원소를 출력 후 pop을 합니다. 이를 Queue가 빌 때까지 진행합니다.

• List로도 풀어보았습니다.

Code

제출 날짜

2021/04/25

메모리

2148 KB

시간

64 ms

#include <iostream>
#include <queue>

std::queue<int> q;
int N, K;

void io_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	io_faster();
	std::cin >> N >> K;
	for(int i = 1 ; i <= N ; i++)
		q.push(i);
}

void solve()
{
	std::cout << "<";
	while(!q.empty())
	{
		for (int i = 0 ; i < K - 1 ; i++)
		{
			q.push(q.front());
			q.pop();
		}
		std::cout << q.front();
		q.pop();
		if (!q.empty())
			std::cout << ", ";
	}
	std::cout << ">";
}

int main()
{
	input();
	solve();
	return (0);
}