백준 c++ 1158 문제 풀이

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

목차

1. 설명

 

2. 내 코드

 

3. 문제 풀이 해석 내용

 

4. 실행 결과

 

설명

백준 실버 4 문제 입니다.

문제명 : 요세푸스 문제

 

내 코드

#include<iostream>
#include<queue>
#include<vector>
#include<string>

using namespace std;

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

	int n, k;
	cin >> n >> k;
	queue<int> que;
	for (int i = 1; i <= n; i++) 
	{
		que.push(i);
	}
	cout << '<';
	while (que.size() != 1) 
	{
		for (int i = 0; i < k - 1; i++) 
		{
			que.push(que.front());
			que.pop();
		}
		cout << que.front() << ", ";
		que.pop();
	}
	cout << que.front() << '>';

}

 

문제 풀이 해석 내용

 

변수 선언 및 큐 초기화

int n, k; // 총 인원수 n, 제거할 순서 k
cin >> n >> k; // n, k 입력받기

queue<int> que; // 정수형 데이터를 저장할 큐

for (int i = 1; i <= n; i++) // 1부터 n까지 큐에 추가
{
    que.push(i);
}

int n, k; : 총 인원수 n과 제거할 순서 k를 저장하는 변수입니다.
cin >> n >> k; : 사용자로부터 n과 k 값을 입력받습니다.
queue<int> que; : std::queue를 사용하여 1부터 n까지의 사람들을 나타내는 정수들을 저장합니다. 

큐는 원형으로 앉은 사람들을 시뮬레이션하는 데 적합합니다.
for 루프를 사용하여 1부터 n까지의 숫자를 순서대로 큐에 추가합니다. 처음에는 [1, 2, ..., n] 순서로 큐에 들어갑니다.

 

 

요세푸스 순열 생성 및 출력

cout << '<'; // 결과 시작 대괄호 출력

while (que.size() != 1) // 큐에 1명 남을 때까지 반복
{
    // k-1명의 사람을 큐의 앞으로 이동
    for (int i = 0; i < k - 1; i++)
    {
        que.push(que.front()); // 큐의 맨 앞 요소를 맨 뒤로 옮김
        que.pop();             // 맨 앞 요소 제거
    }

    // k번째 사람 제거 및 출력
    cout << que.front() << ", "; // 제거될 k번째 사람 출력 후 쉼표와 공백 추가
    que.pop();                     // k번째 사람 제거
}

cout << que.front() << '>'; // 마지막 남은 1명 출력 후 닫는 대괄호 추가

cout << '<';: 결과 순열의 시작을 알리는 '<' 문자를 출력합니다.
while (que.size() != 1): 큐에 딱 한 명만 남을 때까지 루프를 반복합니다.

안쪽 for 루프 (for (int i = 0; i < k - 1; i++)): k-1번 반복합니다. 

이는 K번째 사람을 찾기 위해 앞에서 K-1명의 사람을 큐의 뒤로 보내는 과정입니다.

que.push(que.front());: 큐의 맨 앞에 있는 사람을 다시 큐의 맨 뒤에 넣습니다.
que.pop();: 큐의 맨 앞에 있는 사람을 제거합니다. 이 두 줄의 작업은 큐의 맨 앞 요소를 맨 뒤로 '이동'시키는 효과를 냅니다.

 

안쪽 루프가 끝나면 큐의 맨 앞에는 K번째 사람이 오게 됩니다.
cout << que.front() << ", ";: 큐의 맨 앞에 있는 K번째 사람(제거될 사람)의 번호를 출력하고, 그 뒤에 ", "를 추가합니다.
que.pop();: K번째 사람을 큐에서 완전히 제거합니다.

while 루프가 종료되면 큐에는 정확히 한 명만 남게 됩니다.
cout << que.front() << '>';: 큐에 마지막으로 남은 사람의 번호를 출력하고, 결과 순열의 끝을 알리는 '>' 문자를 출력합니다.

 

 

실행 결과