[파이썬] 11866, 1158 요세푸스 문제

메모리만 다르지 두 문제는 같은 문제이다

 

심지어 출력도 같다

 

사실 이 문제는 나에게 있어서는 좀 묵힌 문제이다 

 

3주 전 파이썬 처음 시작하면서

 

solved에서 단계별로 재밌는 문제없나 하면서 둘러보던 도중

 

요세푸스 문제가 눈에 띄었다.

 

 

그게 이 문제

 

1, 2, 3, 4, 5, 6, 7 > 3, 6, 2, 7, 5, 1, 4

 

이 문제를 왜 묵혔냐면..

 

풀리지가 않았기때문이다 ..

 

그렇게 배열 문제들도 좀 풀고 실버 문제들을 조금씩 돌고 오다 보니

 

3가지 정도 방법이 스쳤다 

 

 - 배열을 5천 개 잡아봐야 계산할 것도 아니라서 1초 안에 풀릴 것이니 미리 수 배정

 

그래서 처음 나온 접근법은

 

 

1. 배열을 돌면서 해당 인덱스에 true를 줘서 중간에 가다 true 가있으면 +해줘서 더한 수의 인덱스만큼 출력

 

사실 요건 실패했다 하다가 뭐가 뭔지 몰라서 그냥 코드를 지웠다.

 

 

2. 배열을 하나 더 줘서 예시에 있는 값을 돌리면서 다른 배열에 있는 수가 나오면 +값을 줘서 출력

 

이거 하다가 또 화딱지가 나서 소주 한 병 마시고 자버렸다.. 

 

몇일 뒤 다시 보면서..

 

'굳이.. 넣을 필요 있나?'

 

그래서 3번째는

 

deque를 이용한 코드를 짜 보기로 했다 

 

from collections import deque mx, num = map(int, input().split()) ary = deque([x for x in range(1, mx+1)]) #0, ///1 2 3 4 5 6 7 ans =[] while (1):     if len(ary) ==0:         break         ary.rotate(-num)     ans.append(str(ary.pop())) print ("<"+', '.join(ans)+">")

매우 간단하다

 

예시가 7, 3일 때

 

그냥 미리 배정된 값에서 rotate로 3씩 돌려가면서 

 

나오는 값을 pop하면서 정답 배열에 넣고 while문이 끝나면

 

그걸 join으로 출력해버리는 것이다 

 

 

 

이후에 16mb짜리 요세푸스 문제를 풀러 갔는데 

 

아무리 봐도 16mb는 넘을 것 같아서 저 코드로는 시도하지 않았다.. 

 

뭔가 모르는 새로운 식이 있나 보다