[c++ | 백준] 1158번 요세푸스 문제

 

 

c++ 문제풀이

 

 

---

 

 

 

[백준 1158번 요세푸스 문제]

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

 

 

---

 

풀이 코드

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

int main(void)
{
    queue<int> q;
    int n, k;
    int cnt = 1;

    cin >> n >> k;

    for (int i = 1; i <= n; i++)
        q.push(i);

    cout << "<";

    while (q.size() != 0)
    {
        for (int i = 1; i < k; i++)
        {
            q.push(q.front());
            q.pop();
        }

        cout << q.front();

        if (q.size() != 1) cout << ", ";

        q.pop();
    }
    cout << ">";

    return 0;
}

 

먼저 저는 큐로 풀어보았습니다. 큐에 n명의 사람들을 차례대로 넣고 앞에서 부터 확인을 합니다.  k번째 사람이 되기 전 까지 List 뒤로 사람을 넣어주고 앞에 남은걸 지워주는걸 반복하여 k번째 사람이 큐의 맨 앞으로 오게 만들어줍니다. 큐의 맨 앞으로 온 k번째 사람을 출력하고 pop하여 List에서 지워줍니다. 모든 사람이 pop되어 지워질 때 까지 반복하면 계속하여 k번째 사람을 빼낼 수 있게 됩니다. 꺽새는 while문의 시작과 끝에 넣어주면 깔끔하게 출력이 됩니다.

 

 

밑은 이 문제를 List로 원형큐를 구현해 풀어본 코드입니다.

 

 

---

 

 

List로 구현한 원형큐로 풀어본 코드

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

int main()
{
	ios::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k;
	list<int> circleList;

	cin >> n >> k;

	for (int i = 1; i <= n; ++i)
		circleList.push_back(i);

	list<int>::iterator target = circleList.begin();

	cout << '<';
	while (n > 0)
	{
		for (int i = 1; i < k; ++i)
		{
			target++;
			if (target == circleList.end()) target = circleList.begin();
		}
		if (n == 1)
		{
			cout << *target;
			break;
		}
		cout << *target << ", ";
		n--;
		target = circleList.erase(target); // erase는 지운 값의 다음 주소를 반환
		if (target == circleList.end()) target = circleList.begin();
	}
	cout << '>';
}

 

위와 같이 List에 n명의 사람들을 차례대로 넣고 target이라는 이름의 List의 begin을 가리키는 반복자를 만들어 놓았습니다. target은 k번째 사람인지 확인할 수를 가리키게 만들 것 입니다. 그래서 처음엔 begin을 가리키게 만들어 놓은 것 입니다. 이제 k번째 사람를 찾을 때 마다 출력을 하게 만들겁니다. 위에 처럼 k번째 사람가 오기 전까지 target++을 하여 target이 결과적으로 k번째 사람을 가리키게 합니다. 여기서 주의할 점은 target++을 한 뒤에 target이 가리키는 주소가 List의 끝일 때 오류가 나기 때문에 그럴 때는 target을 다시 begin을 가리키게(원형큐) 합니다. 그리고 남은 사람이 1명이라면 출력을 하고 while문을 나갑니다. 남은 1명이 아니라면 출력을 하고 인원을 한명 줄입니다. 그리고 List에서 target을 지우고 target이 지금 지운 사람의 다음 주소를 가리키게하여 반복을 하면 되는데 이때 다시 주의 할게 지운 사람의 다음 주소가 List의 끝일 때 target을 begin으로 되돌려주어야합니다. 이렇게 하면 List로 원형큐를 구현하여 요세푸스 문제를 풀 수 있습니다.

 

 

원을 이룬 사람들을 빼나가는 문제여서 원형큐를 생각하여 풀이 할 수 있다는 것!