[백준] [파이썬/Python] 11866번 : 요세푸스 문제 풀이

[백준] [파이썬/Python] 11866번 : 요세푸스 문제 0

문제

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

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

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

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

입출력

---

문제 해석(풀이)

• N=7, K=3이라고 예시를 둔다.
• 이 문제를 풀이하면, (N)7명의 사람이 원을 이루면서 앉아있고, 3번째(K)가 될 사람을 계속 제거한다.

• 그림을 순서대로 따라가면, (매번 3번째에 사라짐)
  1. 1→2→3을 가서 3이 사라진다
  2. 다시 4→5→6을 가서 6이 사라진다
  3. 다시 7→1→2를 가서 2가 사라진다.
  4. 다시 4→5→7을 가서 7이 사라진다.
  5. 다시 1→4→5를 가서 5가 사라진다.
  6. 다시 1→4→1을 가서 1이 사라진다.
  7. 다시 4→4→4를 가서 4가 사라진다.
• 이 풀이를 이용해서 해결해보자.

코드

from sys import stdin

N, K = map(int,stdin.readline().split())
index = 0
array = list(range(1,N+1))
result = []

while len(array) != 0: # 리스트 수가 0이 아니면 반복
    index += (K-1)
    index = index % len(array)
    result.append(array.pop(index))

## 문자
print("<",end="")
for i in range(N-1):
    print(result[i],end=", ")
print(result[N-1], end = "")
print(">",end="")

• 입력, 초기화
  1. N,K를 입력받는다.
  2. index를 0으로 초기화한다 (후에 index로 구분할 것이기 때문)
  3. array에 1부터 N까지 초기화하여 리스트로 만든다.
  4. result는 결과를 넣을 리스트

---

• while문
  1. 리스트의 요소가 끝날때까지 반복시킨다
  2. index에 K-1한 값을 더해준다.
     1. 왜냐하면, K가 3인 경우라고 쳤을 때
     2. 처음 인덱스는 2이다. 그리고 요소가 삭제되면 여전히 인덱스는 2지만 삭제된 이후의 리스트이기 때문에 이미 1칸을 갔다고 볼 수 있다. 따라서 앞으로 2칸만 이동하면 된다.
  3. index의 범위를 %를 이용해서 리스트 크기에 맞게 조정해줬다.
  4. result에 array에서 한 명을 제거하는 동시에 (pop) append해줬다.

---

• 결과 출력
  • 이 문제는 이상하게 출력이 <결과> 이런식으로 < > 괄호를 써서 결과출력이 매우 귀찮다. 그냥 차근차근 출력하면 된다.
  • print(”출력할거” ,end=””)
    • print 함수 안에 end를 써서 print의 끝이 어떤 걸로 끝날지 지정할 수 있다.

---

잡담

• 처음에 문제를 잘 못 이해해서 3번째 자리가 이어져서 제거되야 하는데 계속 3번째 자리가 제거되는줄 알고 이게 뭐지 ? 싶었다
• 풀어서 다행이당