백준 #28066.타노스는 요세푸스가 밉다 : 큐 / 실버2

문제 링크 :https://www.acmicpc.net/problem/28066

🔍 Inspection

문제 접근(문제 분석 → 풀이 아이디어)

• 유형 : 큐

• 문제 요약

  i. 첫번째 ~ K 마리 선택하고, 첫번째를 제외한 2~ K 번 청설모 제거한다. ii. if 남은 청설모 < K 라면, "첫번째만 남긴다."(위와 동일) iii. if 남은 청설모가 2마리 이상이면, 다음 오른쪽 청설모가 첫번째 청설모로 선정 iv. 위 과정을 총 청설모가 1 마리만 남을 때 까지 계속한다. v. 입력 : 청설모 총 마리 N , 그룹화할 K 마리 ->출력 : 최후 1인 청설모의 번호 반환

🚩 FLOW

코드를 풀이할 때 적었던 플로우가 있나요?

• 시간 초과를 방지하리 위해 큐의 popleft()을 활용해야한다.

1. N,K 입력 변수 정의하고 , 큐 elements 초기 청설모 번호들 1~ N 로 초기화한다.
2. 반복문 while 으로 청설모 1마리만 이하 남을때 까지 탐색을 진행한다.
   1. 남은 청설모 < K 라면 , 첫번째 청설모 번호(element[0]) 만 출력하고 종료한다.
3. 첫번째 순번 청설모를 변수 first 에 저장하고 , popleft() 로 첫번째를 포함한 K 마리 청설모를 elements에서 제거한다.
4. 기존 첫번째 요소를 append() 로 맨 뒤에 추가하여, 다음 첫번째 요소는 자동으로 elements 의 idx =0 로 배치된다.

🚩제출한 코드

import sys
from collections import deque
input = sys.stdin.readline

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

elements = deque([i for i in range(1, N+1)])
start = 0 
while len(elements) > 1 : # 탐색 종료 조건 : 청설모가 1마리 이하로 남을 떄 

  if len(elements) < K : # K보다 적게 남아있으면, 강제종료
    print(elements[0])
    exit()
  # elements 개수 >= K
  first = elements[0]
  # 1. K개 삭제(first 도 포함해서 일단 삭제) 
  for i in range(K): # K-1 개 삭제

    elements.popleft()

  #2.기본 첫번째 요소를 맨 뒤쪽에 추가,  
  # 다음 첫번째 요소는 자동 맨 앞(idx= 0 )으로 배치됨
  elements.append(first)

  
print(elements[0])

• 💥 1차 제출