[백준 1158] 요세푸스 문제

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

1158번: 요세푸스 문제

[알고리즘]

큐의 개념을 이용한다. 큐는 FIRST-IN, FIRST-OUT 이다. 

따라서 k주기가 아닐때는 delete한다음 큐에 다시 집어넣어 주고 k주기일때는 그냥 delete해주면 된다. 

 

python3로 제출했을때는 시간초과가 떠서 실패하였고 pypy3로 제출하니 성공하였다. 

 

시간초과가 난 이유를 다음과 같은 이유라고 예상하였다.

n=3, k=3일때를 생각해보면

 

[인덱스] 012

[값]       123 (초기 큐)

 

[인덱스] 0123

[값]        231 

 

[인덱스] 01234

[값]          312 

 

[인덱스] 01234

[값]           12 

 

[인덱스] 012345

[값]             21 

 

[인덱스] 0123456

[값]              12 

 

[인덱스] 0123456

[값]                2

 

[인덱스] 01234567

[값]                  2

 

[인덱스] 012345678

[값]                   2

 

[인덱스] 012345678  //배열 크기 최소 9개 

[값]                   

 

배열 크기가 최소 9개여야 한다. 

이렇게 된다면 이 문제의 최소 큐의 크기는 5000*4999이 되어야 하는데 너무 크고 공간의 낭비도 크기 때문에 시간초과가 난 것이 아닌가 예상하고 있다.

 

메모리와 시간이 많이 소비되서 순환 큐로 다시 코드를 작성해봤다.