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

 

 

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)

출력

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

링크

11866번: 요세푸스 문제 0 (acmicpc.net)

11866번: 요세푸스 문제 0

 

 접근 방법

1. 두 개의 정수를 입력 받고
2. 사람 리스트 생성
3. 리스트가 0이 될 때까지 (while문)
4. 사람을 제거하는 규칙 실행
   
   1. 인덱스는 입력 받은 정수와 리스트의 길이에 따라 계산
   2. 제거하는 사람은 pop으로 원소 삭제

+ 큐 참고 자료 : [자료구조] 큐, 스택 / queue, stack — y-seo의 딩코 기록들 (tistory.com)

[자료구조] 큐, 스택 / queue, stack

 

 풀이

1. Map 함수

이 문제에서는 정수 2개를 한 줄에 입력 받아야 한다. 따라서 입력된 문자열을 우선 split()함수로 분리해준다. 이후 이 정수 2개를 저장하는데.. 물론 리스트에 저장하여 인덱스로 접근해도 가능하다.

str = list(sys.stdin.readline().split()) #두 개의 정수 입력 받기
n = int(str[0]) #각각 변수에 저장
k = int(str[1])

그러나 더 단축 가능한 방법은 map() 함수의 이용이다.

map(function,iterable)

map() 함수는 리스트 요소(iterable)를 원하는 함수(function)로 바꾸어 새 리스트로 생성한다.

따라서 이 문제에서는 다음과 같이 사용하였다.

n,k = map(int, sys.stdin.readline().split()) #두 개의 정수 입력 받기

띄어쓰기 단위로 입력받은 문자열을 잘라 int형으로 변환 후 n,k에 각각 저장한다.

2. 리스트의 인덱스 계산

인덱스는 입력 받은 값(k)만큼 증가되는데 동시에 사람이 제거되며 리스트의 길이가 줄어 단순히 덧셈 계산으로는 IndexError가 생긴다.

따라서 인덱스 변수(i)에 입력 받은 값(k)를 더해주고 사람이 제거되니 1을 빼주고 그 값을 리스트의 길이(len(p))로 나누어 나머지 값만을 가지고 인덱스에 접근해야 한다.

i = (i + k - 1) % len(p) #인덱스 계산

 

 

 전체코드

import sys

n,k = map(int, sys.stdin.readline().split()) #두 개의 정수 입력 받기
p = [i for i in range(1,n+1)] #리스트 생성
i = 0
print("<", end="")
while len(p)!= 0:
    i = (i + k - 1) % len(p) #인덱스 계산
    if len(p) == 1: #마지막 사람
        print(p.pop(i), end="")
    else: #제거되는 사람
        print(p.pop(i), end=", ")
print(">")