Classic_Blue_Note

문제

www.acmicpc.net/problem/1158

풀이

해당 문제는 비교적 간단한 solved.ac 기준 실버 5급 문제로, 처음에는 원형 큐를 사용해야 할 지 고민했지만, 조금 생각해 보니 굳이 원형 큐를 구현할 필요 없이, 리스트와 인덱스 포인터만을 이용하여 간단하게 해결할 수 있다.

필자의 경우, 우선 사람 배열을 만들고, 제거할 사람의 위치를 가리키는 인덱스 포인터를 지정했다. 그리고 해당 인덱스 포인터에 K값을 더해 가면서, 해당 값이 사람 배열의 크기보다 커지면 나눠 줘 가면서 원형으로 이동하는 것을 표현했다.

그리고 사람을 빼낸 다음, 빼낸 사람을 그대로 요세푸스 배열에 추가한다. 이때 사람을 빼낸 후 인덱스 포인터를 1만큼 감소시켜야 하는데, 그 이유는 사람을 빼내면서 자연스럽게 인덱스 포인터가 다음 사람을 가리키게 되기 때문에, 다음 사람을 1번째 사람으로 표현하기 위해서는 인덱스 포인터를 함께 1만큼 감소시켜 줘야 한다.

출력 형식에서 약간의 문제가 있었는데, 파이썬 메소드 중 __str__ 메소드를 이용하여 간단하게 해결하였다. 리스트의 경우 __str__ 메소드를 거치면 [a, b, c] 형태로 출력되기 때문에, 해당 메소드를 호출한 뒤 맨 앞과 맨 뒤의 문자만 제거하고, 해당 부분에 <, >를 넣어 출력하는 식으로 해결하였다.

코드

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

people = []
for i in range(N):
    people.append(i+1)

yosep = []
people_index = -1

while True:
    people_index += K
    people_index = people_index % len(people)
    yosep.append(people.pop(people_index))
    people_index -= 1
    if len(people) == 0:
        break

print("<{}>".format(yosep.__str__()[1:-1]))