[BOJ] 1158번 - 요세푸스 문제

---

문제설명

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

1158번: 요세푸스 문제

사고과정

• 처음에 while 무한 루프로 구현했지만 시간초과 케이스가 발생.. 
• 그래서 index가 배열 범위를 넘어갈 때 다시 0번 인덱스로 돌아가게 하기 위해서 %연산을 쓰긴 해야할 것 같다는 아이디어는 생각했지만 코드로 구현해내지 못했다..
• 구글링해 보니 명쾌하게 이해가 되었는데, 예를 들어 index = 7 이고 len(array) = 5다 라고하면은, 7 % 5 가 의미하는 바는 길이가 5인 배열에서 7번 인덱스를 찾아야 하는데 길이 범위를 넘으니 7을 5로 나눈 나머지인 2번 인덱스 값으로 가라!는 의미이다! 잊지 말자!(단, 배열의 길이가 매번 1개씩 줄어들기 때문에 가능!)

풀이(스스로 못 푼 풀이)

import sys

input = sys.stdin.readline
n, k = map(int, input().split())
array = [i for i in range(1, n+1)]

result = []
index = 0

for _ in range(n):
    index += (k-1)
    if index >= len(array):
        index %= len(array)
    result.append(str(array.pop(index)))

print('<'+', '.join(result)+'>')

 

다시 한번 푼 풀이

n, k = map(int, input().split())
array = [i for i in range(1, n+1)]
stack = [0]  # 스택에는 index 넣기
result = []

while len(array) != 0:
    index = stack.pop() + (k-1)
    if index >= len(array):
        index %= len(array)
    result.append(str(array.pop(index)))
    stack.append(index)

print('<'+ ', '.join(result) +'>')