[자료구조] 6일차 큐로 풀 수 있는 문제

주문 처리하기

: 주문을 들어온 순서대로 처리. 단 vip의 주문은 우선 순위가 높음

: 주문에 대한 정보는 (t, d) 형태로 주어지

며 t는 주문이 접수되는 시각, d는 주문을 처리하는 데 드는 시간

 

 

요세푸스 순열

• 1번부터 n번까지 번호를 가진 n명이 있다.
• 1번부터 순서대로 세었을 때 k번째 사람을 원에서 제거
• 제거된 사람의 다음 사람부터 k번째 사람을 원에서 또 제거 ..반복
• 제거된 사람들의 번호를 순서대로 나열한 것을 요세푸스 순열이라고 함.

 

 

💡 요세푸스 순열 과정

 

 

💡 원을 k - 1번 반시계 방향으로 회전 시켰을 때 12시 위치에 있는 사람이 제거되는 걸로 바꾸기

• 12시에 있는 사람을 시작으로 보고, 1번부터 n번까지 큐에 저장.
• 큐에 저장된 자료가 모두 제거될 때까지 아래 작업 반복
  • (a) 큐를 출력(pop)하고, 출력된 수를 다시 큐에 입력(push)한다.
  • (b) 큐를 출력(pop) 한다.
  • (c) (b)에 의해 출력된 수를 순서대로 저장한다.

 

• 원이 회전하면 큐에서 자료를 출력한 후 그 자료를 큐에 입력해 주면 됨.
• 선입선출 자료구조라 맨 앞 요소가 제거됨.