1158번 - 요세푸스 문제

💡 반례를 잘 찾는 습관이 필요하다!!

<오답 코드>

import sys

input = sys.stdin.readline

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

circle = [i+1 for i in range(N)]
answer = []

idx = 0

while circle:
    
    idx = (idx + K - 1) % len(circle)
    
    answer.append(circle.pop(idx))
    
for idx,val in enumerate(answer):
    if idx == 0:
        print("<", end ='')
        print(val, end=", ")
    elif idx == N-1:
        print(val, end='')
        print(">")
    else:
        print(val, end= ', ')

• 위 코드는 97%에서 오류가 발생하였다.. 97%에서의 문제라면 거의 출력값에서 문제가 생겼다고 생각하였다.
• 고민하던 중 반례를 찾을 수 있었다. 바로 1 1이 입력되면, "<1, >" 이런식으로 출력된다는 문제점이 있었다.
• 그리하여 출력값의 수정을 하였다.

<정답 코드>

import sys

input = sys.stdin.readline

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

circle = [i+1 for i in range(N)]
answer = []

idx = 0

while circle:
    
    idx = (idx + K - 1) % len(circle)
    
    answer.append(circle.pop(idx))
    
print("<", end ='')
    
for idx,val in enumerate(answer):
    
    if idx == N-1:
        print(val, end='')
    else:
        print(val, end=', ')
    
print(">")

• 위의 문제는 처음에는 삭제를 진행하여도 삭제된 다음것의 꼬리를 물도록 할 수 있는 circular Linked List를 생각하였다.
• 하지만 역시 코딩테스트의 시간적인 측면에서 직접 구현하는 건 어렵다고 생각하였고, 그때 그때 pop()을 해줄 수 있는 리스트를 사용하였다.
• 출력은 처음에 <와 >는 무조건 들어가니 개별적으로 출력해주고,나머지는 조건에 맞게 마지막꺼만 end = '' 로 지정하고 나머지는 end =', '로 지정하였다.