[Python-CodingTest] 5-5. 공주 구하기 (큐)

공주 구하기

문제 정리

입력

8 3

처리 과정

1. k번째 수를 외치는 사람은 제외된다고 하면, k-1번째까지 외치는 사람은 통과
2. k-1번째 까지는 popleft() 하고 큐의 뒤쪽으로 append()
3. k번째 수를 외치는 사람은 뒤에 붙이지 않고 popleft()만!
4. 큐의 요소가 1일 때 dq[0]을 출력

출력

7

내 답

import sys
sys.stdin = open("./input/in5.txt", "rt")

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

lst=[] # 왕자 리스트

save=n # 남은 사람 수
num=1 # 각각의 왕자가 외치는 번호

# 리스트 초기화
for i in range(n):
    lst.append(i+1) # [1, 2, 3, 4, 5, 6, 7, 8]
# lst=list(range(n)) # [0, 1, 2, 3, 4, 5, 6, 7]

while save>1:
    for x in lst:
        if num!=k:
            num+=1
        else:
            lst.remove(x)
            save-=1
            num=0

res=''.join(map(str,lst)) # 리스트를 스트링화
print(res)

큐를 사용하지 않았음..

풀이

import sys
from collections import deque # deque라는 자료구조를 사용하기 위해 임포트
sys.stdin = open("./input/in5.txt", "rt")

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

dq=list(range(1,n+1)) # 1부터 n으로 초기화
dq=deque(dq) # 리스트를 큐로 변환

while dq: # 큐가 비면 while문 종료
    for _ in range(k-1):
        cur=dq.popleft() # cur는 현재 숫자를 외치는 사람
        dq.append(cur) # 큐의 뒤쪽으로 append
    dq.popleft() # 다음 차례인 사람은 k번째 수를 외치게 되므로 큐에서 제외

    # 큐에 마지막 남은 사람을 출력
    if len(dq)==1:
        print(dq[0])
        break
        # 마지막 사람을 pop 함으로써 while문 조건 위배 -> 종료
        # dq.popleft() # 이렇게도 가능

정리

• from collections import deque: deque 라이브러리 사용하기 위해 임포트

  appendleft(): 왼쪽으로 append
  popleft(): 왼쪽으로부터 pop
  append(): 오른쪽으로 append
  pop(): 오른쪽으로부터 pop
  

• 큐라는 자료구조를 사용하기 위해서는 append()와 popleft() 사용!
• deque(lst): 리스트를 큐로 변환
• list(range(1,n)): 리스트 1부터 n-1까지로 초기화

  list(range(1,11))이라면 lst에는 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기