백준-1158-요세푸스 문제

구현

(N , K)

1 2 3 4 5 6 7    :: 3      

1 2 4 5 6 7      :: 6      

1 2 4 5 7        :: 2     

1 4 5 7          :: 7      

1 4 5            :: 5      

1 4              :: 1      

4                :: 4

 

위와 같이 동작과정을 나열해보면 이것이 원형 큐 방식으로 동작하는 것을 알 수 있다.

그래서 idx가 리스트의 값을 넘어갔을 때 % 연산자를 활용하는 것이 포인트인 것 같다.

---

구현 코드 

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

n = [i for i in range(1,N + 1)]
result = []

idx = 0

while True:
    if len(n) == 0:
        break

    idx += (K - 1)
    idx %= len(n)

    # result.append(str(n[idx]))
    # n.remove(n[idx])
    result.append(str(n.pop(idx)))



print('<', end="")
for i in range(len(result)):
    if i == len(result) - 1:
        print(str(result[i]) , end='')
    else:
        print(str(result[i]) , end=', ')
print('>', end="")

# print('<', ', '.join(result), '>' , sep="")

 

처음에는 pop을 사용하지 않고, 리스트의 remove와 append를 통해서 문제를 구현했다.

당연하게도 이 방법과 pop연산자를 사용하는 방법은 아주 많은 시간차이가 난다.

이유는 pop은 요소를 제거하면서 return값도 가지기 때문이다.

 

또한     idx += (K - 1) % len(n)  이라고 초반에 구현을 했을 때 올바른 값이 나오지 않았다.

이는 idx = idx + (K-1) % len(n)이 되기 때문에 % 연산자가 우선 연산이 된다. 이것 또한 당연한 것이다..

 

추가적으로 해당 문제의 출력은 <1,2,3> 과 같은 형식의 출력이 필요하다.

이럴 경우 join 연산자를 활용할 수 있음을 기억하자

 

 

문제링크