백준 1158번 요세푸스 문제

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

1158번: 요세푸스 문제

순열을 하나씩 제거하는 문제

 

큐를 사용하여 풀어야할 거 같지만 사용하진 않았다.

# 입력 받기
n, k = map(int, input().split())

# 초기화
arr = []
for i in range(1, n+1):
    arr.append(i)
count = 0

# 순열의 원소 제거 진행
print('<', end='')
while arr:  # 배열이 비어있을 때까지
    count += k-1    # 현재 원소가 하나 없어지므로 k-1 씩 더해줌
    while count >= len(arr):    # 범위 초과시 인덱스를 맞춰줌
        count -= len(arr)
    if len(arr) != 1:
        print(arr.pop(count), end=', ')  # pop하며 출력
    else:
        print(arr.pop(count), end='>')

사용할 순열에 1 ~ n 의 값을 넣고

제거할 k번째를 계산하는 변수 count를 0으로 초기화한다.

 

while 문으로 배열이 비어있을 때까지 제거를 반복한다.

원소를 하나 제거하면서 넘어가니까 count에는 k-1을 더한다.

범위 초과시 인덱스를 조절해주고

조절한 인덱스의 원소를 pop하면서 출력한다.

 

간단한 문제였지만 testcase가 크다면 시간초과가 날 수도 있을 거 같다.

큐로 푸는 방법도 익혀야할 거 같다.