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

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

1158번: 요세푸스 문제

 

 

요세푸스 문제이다.

 

문제 설명

요세푸스 문제는 다음과 같다.

 

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

 

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

 

 

문제 해석 및 설명

처음에 문제를 제대로 이해를 못했다. 

이렇게 그려놓고 멈췄는데, 그래서 요세푸스 문제를 나무위키로 봤다.

원으로 둘러쌓아앉아서 한명 건너 뛰고, 그 다음 한명 죽이고, 한명 건너뛰고 이런식으로 반복했다고 하니, 이해가 됐다.

즉, 

이런 느낌 이다.

 

요세푸스 순열을 프로그래밍 하는 문제이다.

예를 들어, 7명의 사람이 있고 3번째 사람을 계속 제거한다면
1, 2, [3], 4, 5, 6, 7 --> 3 제거
1, 2, [3], 4, 5, [6], 7 --> 6 제거(6이 제거된 다음 7이 첫번째가 됨)
1, [2], [3], 4, 5, [6], 7 --> 2 제거
1, [2], [3], 4, 5, [6], [7] --> 7 제거
1, [2], [3], 4, [5], [6], [7] --> 5 제거
[1], [2], [3], 4, [5], [6], [7] --> 1 제거
[1], [2], [3], [4], [5], [6], [7] --> 4 제거
<3, 6, 2, 7, 5, 1, 4> 순열이 요세푸스 순열을 의미한다.

 

프로세스 흐름

[1, 2, 3, 4, 5, 6, 7] => queue로  push
[2, 3, 4, 5, 6, 7, 1] => queue로  push
[3, 4, 5, 6, 7, 1, 2]
3 => queue를 pop하고, result_list 에 넣기

[4, 5, 6, 7, 1, 2] => queue로  push
[5, 6, 7, 1, 2, 4] => queue로  push
[6, 7, 1, 2, 4, 5]
6 => queue를 pop하고, result_list 에 넣기

[7, 1, 2, 4, 5] => queue로  push
[1, 2, 4, 5, 7] => queue로  push
[2, 4, 5, 7, 1]
2 => queue를 pop하고, result_list 에 넣기

[4, 5, 7, 1] => queue로  push
[5, 7, 1, 4] => queue로  push
[7, 1, 4, 5]
7 => queue를 pop하고, result_list 에 넣기

[1, 4, 5] => queue로  push
[4, 5, 1] => queue로  push
[5, 1, 4]
5 => queue를 pop하고, result_list 에 넣기

[1, 4] => queue로  push
[4, 1] => queue로  push
[1, 4]
1 => queue를 pop하고, result_list 에 넣기

[4] => queue로  push
[4] => queue로  push
[4]
4 => queue를 pop하고, result_list 에 넣기

 

 

계속 시간 초과가 떴다.

1. 앞에 두번째 시간초과는 중간에 변수의 이름을 바꿔줬는데, while문 안에 없어져버린 미처 바꾸지 못했다..

So, 휴먼에러,,

 

2. 그 이후에는 queue.pop(0)의 연산이 시간 복잡도가 O(n)이 나와서 좋지 않다는 것을 알았다.

백준 1158번 요세푸스 문제 파이썬에서 나는 처음에 이렇게 작성했다.

틀린 풀이는 아니지만, 계속해서 append, pop 함수를 사용하고, 반복문을 오래 도니 시간 초과가 뜨는 것 같다.

import sys
input = sys.stdin.readline

K, N = map(int, input().split())

K = int(K)
N = int(N)

queue = [i for i in range(1, K+1)]
result_list = []

count = 0
while(1):
    print queue
    if(len(queue)==1):
        result_list.append(queue.pop(0))
        break
    count += 1
    if(count == N):
        result_list.append(queue.pop(0))
        count = 0
    else:
        queue.append(queue.pop(0))

print result_list

문제점 

- pop의 시간 복잡도

=> collections deque를 사용해서 해결해보자.

 

deque란 

Deque(데크)는 double-ended queue 의 줄임말로, 앞과 뒤에서 즉, 양방향에서 데이터를 처리할 수 있는 queue형 자료구조를 말한다.

python에서 collections.deque는 list와 비슷하다. list의 append(), pop() 메소드는 deque에서도 제공한다.collections.deque의 자세한 설명은 docs.python.org에서 확인할 수 있다.

- List.append(x)와 마찬가지로 를 deque의 오른쪽(마지막)에 삽입해준다.

- List.pop()과 같이 오른쪽(마지막)에서 부터 차례대로 제거와 반환(remove and return)을 하는 메소드이다.

- pop()의 반대로, 왼쪽(앞쪽)에서 부터 차례대로 제거와 반환(remove and return)을 하는 메소드이다.

이런 메소드를 사용해서,

가보자구!

 

수정한 코드

from collections import deque

import sys
input = sys.stdin.readline

K, N = map(int, input().split())

K = int(K)
N = int(N)

queue = deque([i for i in range(1, K+1)])
result_list = []

count = 0
while(queue):
    if(len(queue)==1):
        result_list.append(queue.popleft())
        break
    count += 1
    if(count == N):
        result_list.append(queue.popleft())
        count = 0
    else:
        queue.append(queue.popleft())

print('<' + ', '.join(map(str, result_list)) + '>')

 

 

+

처음에 <1, 2, 3> 이런식으로 출력을 해주어야 했을 때, 아래와 같이 코드를 작성해주었는데,

한줄로 줄일 수 있다.

print("<", end='')
for i in range(0, len(result_list)-1):
    print(result_list[i], end=', ')
print(result_list[len(result_list)-1], end='')
print(">", end='')

python map을 잘 활용하면, 좋을 것 같다.

print('<' + ', '.join(map(str, result_list)) + '>')

 

 

 

다른 코드

사실 처음에 내가 계속 이렇게 해보려고 했었는데, 계산이 잘 안되어서 list append, pop으로 진행했는데

어렵당..

import sys

N, K = map(int, sys.stdin.readline().split())
q = []
result_list = []
queue = [i for i in range(1, K+1)]
idx = 0

for i in range(N):
    idx += K-1
    if idx >= len(queue):
        idx = idx % len(queue)

    result_list.append(queue.pop(idx))
print('<' + ', '.join(map(str, result_list)) + '>')

처음에 index 를 0으로 초기화 해주고, K-1의 값을 더해준다.

만약에 index의 값이 queue의 길이보다 크다면, (원 형태이기 때문에) 나눈 나머지를 다시 저장해준다.

 

그러면 result_list 에 해당 index의 값을 넣어주고, queue 에서는 해당 index의 값을 제거(pop)해준다.

 

 

---

나는 약간 계산 등을 할때 어려운 방식으로 접근하는 것 같다..

예전에 디지털시스템 구현할 때, 어려운 방법이 있는데, 쉬운 방법보다 그거를 먼저 생각해내서 골머리를 앓았다.

그 사고를 확장시켜서 넓히거나, 쉬운 방법으로 생각을 해보거나 하는 방법으로,,

 

사실 이번에 쉬운 방법으로 생각해보는 방향으로 가려고 했었는데, 시간 초과가 계속 되니

사고를 확장을 어떻게 하면 시킬까? 흠.