백준 파이썬 1158번: 요세푸스 문제

www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

문제 유형: 자료 구조, 큐

 

# Solution 1

n, k = map(int, input().split())
arr = [i for i in range(1, n + 1)]
answer = []
num = k - 1

for i in range(n):
    if len(arr) > num:
        answer.append(arr.pop(num))
        num += k - 1
    elif len(arr) <= num:
        num = num % len(arr)
        answer.append(arr.pop(num))
        num += k -1
        
print("<", ', '.join(str(i) for i in answer), ">", sep = '')

우선 1부터 주어진 n까지의 순열을 만들어준다.

 

원을 도는 주기인 num을 지정해주고, 주기대로 해당하는 인덱스의 값을 제거해준다.

 

만약 위치가 리스트를 넘은 경우 (=한 바뀌를 다 돌았을 경우), 리스트 길이를 주기로 나눈 나머지를 인덱스로 하는 값을 제거해준다.

 

이 부분에서 조금 헷갈렸는데, 세 명 중 다섯 번째 사람을 구하는 방법과 같은 맥락이다. 결국 5를 3으로 나누어준 나머지인 2, 즉 두 번째 사람이 다섯 번째 사람이 되는 원리라고 보면 된다.

 

 

출력 예시

# 잘못된 출력
print("<", ', '.join(str(i) for i in answer), ">") # 결과: < 3, 6, 2, 7, 5, 1, 4 >

# 잘못된 출력
print("<", ', '.join(i for i in answer), ">", sep="") # 결과: TypeError: sequence item 0: expected str instance, int found

# 맞는 출력
print("<", ', '.join(str(i) for i in answer), ">", sep="") # 결과: <3, 6, 2, 7, 5, 1, 4>

print에 변수나 값을 쉼표로 구분해서 넣으면 각 값이 공백으로 띄워져서 한 줄로 출력되는데, 이를 막으려면 구분자(sep)를 사용해야 한다. 또한 리스트 안의 각 항목을 합쳐줄 때는 항목이 정수형이라면 문자열로 변환해주어야 str.join() 메소드를 사용할 수 있다.