[백준 1158] 요세푸스 문제 cpp-py

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
q = [n+1 for n in range(N)]
answer = []

idx = 0
while q:
    idx = (idx + (K-1)) % len(q)
    answer.append(q.pop(idx))

print("<",end="")
for n in range(N-1):
    print("{}, ".format(answer[n]), end="")
print("{}>".format(answer[-1]))

문제
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K가 주어진다.
이제 순서대로 K번째 사람을 제거할 때 제거되는 순서대로 출력하시오

입력
첫째 줄에 N과 K가 빈 칸을 사이에두고 순서대로 입력된다.

출력
<>안에 제거되는 순서대로 출력한다.

---

접근

처음에 사람들이 원모양으로 앉아있는 것을 어떻게 표현할까?라는 생각을 하였다. 하지만 이 문제에서 더 관심을 가져야할 것은 원 모양이 아니라 계속해서 K번째 사람을 제거하는 것이다.

N명의 사람들이 있기 때문에 이 사람들은 어떠한 자료구조에 담아야한다. 

만약 1차원 배열에 담는다고 해보자. K번째 사람을 제거하려면 마지막 인덱스를 고려하여 마지막 인덱스를 벗어나면 0부터 다시 카운트를하여 K번째 사람을 찾아야한다. 코드가 복잡해질 것이다.

 

그 다음 큐를 사용하는 것이다. 큐를 사용하면 현재 앞에있는 사람이 몇 번째에 있는 사람인지만 신경쓰면된다.

K번째 사람이라면 다시 뒤로 넣지않고 K번째 사람이아니라면 다시 뒤에 넣는 것이다. 

 

구현

큐에 순서대로 1번부터 N번까지 넣는다.

그렇다면 큐에는 앞에서부터 1번 사람이 순서대로 정렬된 모양일 것이다.

	int N, K;
	queue<int> q;
	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		q.push(i + 1);
	}

 

이제 N-1번 동안 K번째 있는 사람을 제거하는데 N-1번인 이유는 마지막 사람을 출력할 때는 쉼표와 띄어쓰기가 없기 때문이다. 따라서 N-1번 동안은 제거한 사람 뒤에 쉼표와 띄어쓰기를 표시핟도록 한다.

이제 두 번째 for문에서는 K-1번 동안 앞에사람을 뒤에넣고 제거하는 것을 반복한다. 이 for문이 끝났다면 앞에는 우리가 원하는 K번째 사람이 나타날 것이다.

이때 큐의 앞에있는 사람을 출력하고 제거하도록한다.

	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < K- 1; j++) {
			q.push(q.front());
			q.pop();
		}
		cout << q.front() << ", ";
		q.pop();
	}

---

전체 코드

 

c++

#include <iostream>
#include<algorithm>
#include <vector>
#include<cstring>
#include<queue>
// 2/5
using namespace std;

int main()
{	
	int N, K;
	queue<int> q;
	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		q.push(i + 1);
	}
	
	cout << '<';
	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < K- 1; j++) {
			q.push(q.front());
			q.pop();
		}
		cout << q.front() << ", ";
		q.pop();
	}
	
	cout << q.front() << ">" << endl;
	return 0;
}

 

python

처음에 c++처럼 풀었는데 시간초과가 발생했다. 그래서 아래와 같은 방법으로 풀었다.

시간초과가 발생한 이유는 c++처럼 이중 for문을 사용하여서 그런 것 같다. python은 in연산이 O(n)이다.

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
q = [n+1 for n in range(N)]
answer = []

idx = 0
while q:
    idx = (idx + (K-1)) % len(q)
    answer.append(q.pop(idx))

print("<",end="")
for n in range(N-1):
    print("{}, ".format(answer[n]), end="")
print("{}>".format(answer[-1]))

느낀점

자료구조의 개념과 특징을 정확히 알고있어야 실세계의 데이터를 어떻게 쉽게 구현할지 알게된다.