[큐] 백준 11866번 요세푸스 문제0 with Python3

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

11866번: 요세푸스 문제 0

문제

 

내 풀이 -index 값 이동

n, step = map(int, input().split())

indexstep = step - 1
inistep = step

numlist = list(range(1, n+1))
ans = []


while True:  #인덱스 자체가 같은 간격으로 이동하게 구현했다.

#번외로, step 번 째에 해당하지 않는 것들은 popleft, 후 맨뒤에 append하는
#deque 활용을 했더라면 더욱 깔끔한 코드였을것 같다. 

    if len(numlist) == 1:   #루프가 멈추기 직전 조건 
        ans.append(numlist[0])
        numlist.pop(0)      #이 이후 바로 len(..)이 바로 0이 되기에 사실 아래 조건은
                            #무의미하다.
        
    if len(numlist) == 0: #루프가 멈추는 조건
        break
        
    if indexstep >= len(numlist):  #만약에 인덱스가 범위를 초과하면

        indexstep = indexstep - len(numlist)*(indexstep//len(numlist))

								#적절한 index값으로 줄어들게게 하는 수식

    ans.append(numlist[indexstep]) #원하는 요소들을 ans이라는 list로 담았다.
    numlist.pop(indexstep)         #그리곤 삭제
    
    indexstep += inistep - 1       #리스트가 1 짧아졋기에 index도 줄여준다.


#문제에서 요구되는 괴랄한 출력 양식을 위해

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

해설

index가 계속 빙빙 돌며 원하는 값을 append해 그것을 문제에서 요구하는 형태로 출력했다.

 

내 풀이 2 - deque 활용

from collections import deque

n, k = map(int, input().split())

numlist = deque(list(range(1, n+1)))
ans = []

count = 1
while numlist:

    if count == k:
        ans.append(numlist.popleft())
        count = 1

    else:
        numlist.append(numlist.popleft())
        count += 1


# 답안 출력
print('<', end='')
for i in range(len(ans)):
    print(ans[i], end='')
    if i == len(ans)-1:
        break
    else:
        print(', ', end='')
print('>')

해설

이번엔 deque를 이용해 큐 문제 답게 풀어봣다.  

정답에 비교하면 답안을 출력하는 추가적인 for문이 있는 점이 아쉽다. 리스트도 하나 더 필요하기에 시간이나 메모리나 더 잡아먹는다.

 

 

 

 

정답 풀이

from collections import deque
n, k = map(int, input().split())
s = deque([])

for i in range(1, n + 1):
    s.append(i)
    
print('<', end='')
while s:

    for i in range(k - 1): #입력받은 k 전까지의 요소들을
        s.append(s[0])      #모두 뒤에 붙혀주고
        s.popleft()		    #앞에선 제거한다. 큐가 앞으로 당겨지는 모양새
        
    print(s.popleft(), end='')	#그렇게 맨아래가 k번쨰가되면
                                #이를 출력하고 다음 while으로 넘어간다.
    if s:
        print(', ', end='')
print('>')

출처:https://pacific-ocean.tistory.com/233

 

해석

입력받은 k번째까지 요소를 없애고, 그 요소들을 뒤에 추가해준다.

 

k번째 숫자를 출력해주고 그 요소를 없애준다.

 

요소가 없어질때 까지 반복해준다.

 

deque를 사용한 깔끔한 풀이