[알고리즘/자료구조] 1158번 : 요세푸스 문제 - python

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

 

---

• 문제
• 소요시간: 18분 50초

---

• 설계하기(접근방법) 

1. n과 k를 입력받는다

2. 알고리즘 해석

n = 7, k= 3일 때 앞에서부터 3번째 수를 삭제한다.

1 2 3 4 5 6 7 (3 삭제)

-> 1 2 4 5 6 7

그 후 삭제한 자리에서부터 k(3)번째 수를 삭제한다.

4 5 6 7 1 2 (6 삭제)

-> 4 5 7 1 2

........

<3, 6, 2, 7, 5, 1, 4>

다음과 같은 결과가 나온다.

처음에는 list로 수학적으로 구현하려고 했으나, 자료구조 문제임을 생각해서 큐,deque 를 import하여 사용하기로 했다

deque에 있는 rotate 기능을 사용하면 쉽게 문제를 풀 수 있을 것 같았다.

 

deque.rotate(인자)의 기능?

from collections import deque

que = deque([1, 2, 3, 4, 5, 6, 7, 8])

que.rotate(1)

print(list(que))

-> [8, 1, 2, 3, 4, 5, 6, 7]

인자를 1로 넣어주면 1만큼 원소가 오른쪽으로 1칸 회전한다

이 기능을 이용하여

k번째 수를 가장 앞에 놓으려면 k-1만큼 왼쪽으로 회전시켜야한다.

왼쪽으로 회전시키려면 음수를 추가해주면된다

que.rotate(-(k-1))

-> [3,4,5,6,7,1,2]

와 같은 결과가 나온다.

그 후 가장 왼쪽 원소를 popleft()해주고 이것을 다른 리스트에 저장한다.

que가 빌때까지 반복하면 출력값을 얻을 수 있다.

 

3. 출력부분 <리스트> 형태이다.

str(result)[1:-1]을 이용해 리스트 전후로 괄호, 공백없이 출력할 수 있다

 

 

---

• 코드(출력)

from collections import deque

n, k = map(int, input().split())

result = []
que = deque(i for i in range(1, n + 1))

while (que):
    que.rotate(-(k-1))
    result.append(que.popleft())

print("<" + str(result)[1:-1] + ">")

---

• 얻어갈 부분

1. deque의 rotate메서드에 익숙해졌다. 인자값이 deque에 어떤 영향을 미치는지 고려하자

2. 출력부분에 시간을 6분넘게 사용했다. list를 출력할때 str(result)[1:-1]을 사용하면 좌우 공백 없이 리스트를 출력할 수 있다.