n명이 1번부터 n번까지 차례로 매표소 앞에 줄을 서 있다.
i번 사람은 표를 tᵢ장 사려 한다.
매표소는 한 차례에 줄 맨 앞 사람 한 명에게 표를 최대 m장 판다(남은 필요한 장수가 m보다 적으면 그만큼만).
표를 산 뒤 아직 더 필요하면 그 사람은 줄 맨 뒤로 가서 다시 서고, 다 샀으면 줄을 떠난다.
줄이 빌 때까지 이렇게 할 때, 사람들이 줄을 떠나는 차례대로 번호를 빈칸으로 나눠 한 줄에 출력하라.
3 3 4 3 1
2 3 1
5 2 5 1 4 2 3
2 4 3 5 1
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
줄은 앞에서 빼고 뒤에 넣는 큐예요.
차례가 많아야 100만 번이라 그대로 따라 하면 돼요.
큐를 쓰는 법이 언어마다 달라요: Python collections.deque의 popleft()(리스트의 pop(0)은 뒤의 것을 모두 당겨서 느려요), Java ArrayDeque의 pollFirst()/addLast(), C# Queue<int>의 Dequeue()/Enqueue(), C++ std::queue의 front()/pop()/push().
JavaScript·TypeScript에는 큐가 따로 없어서 shift()를 쓰기 쉬운데 이것도 뒤의 것을 당겨요 — 배열에 넣기만 하고 앞 자리(head)를 옮겨요.
C는 크기 n짜리 배열을 원형 큐로(head = (head + 1) % n) 써요.
줄에는 늘 n명 이하라 n칸이면 충분해요.
크레이콘은 새목록(n, 0)으로 원형 큐를 만들었어요.자리빼기(0)도 뒤의 것을 모두 당기지만, 여기처럼 줄이 1,000명 이하면 100만 번도 충분히 빨라요.
함정 둘: 맨 앞이 아니라 맨 뒤에서 꺼내면(스택) 차례가 뒤집혀요.
그리고 다시 설지는 표를 판 뒤에 남은 장수가 0보다 큰지로 정해요 — 사기 전에 'm장 이상 필요하면 다시 선다'로 물으면 딱 m장 필요한 사람이 한 바퀴 더 돌아요.
from collections import deque n, m = map(int, input().split())need = list(map(int, input().split())) line = deque(range(n)) # 줄에 선 사람의 번호(0부터)left = need[:] # 아직 사야 할 표order = []while line: person = line.popleft() left[person] -= min(m, left[person]) if left[person] > 0: line.append(person) # 더 필요하면 맨 뒤로 else: order.append(person + 1)print(*order)const [n, m, ...need] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // 배열 + 앞 자리(head)로 큐를 만든다. shift()는 뒤의 것을 모두 당겨서 느릴 수 있다.const line = [];for (let i = 0; i < n; i++) line.push(i);let head = 0;const left = need.slice();const order = [];while (head < line.length) { const person = line[head++]; left[person] -= Math.min(m, left[person]); if (left[person] > 0) line.push(person); // 더 필요하면 맨 뒤로 else order.push(person + 1);}console.log(order.join(" "));import { readFileSync } from "node:fs"; const [n, m, ...need]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // 배열 + 앞 자리(head)로 큐를 만든다. shift()는 뒤의 것을 모두 당겨서 느릴 수 있다.const line: number[] = [];for (let i = 0; i < n; i++) line.push(i);let head = 0;const left: number[] = need.slice();const order: number[] = [];while (head < line.length) { const person = line[head++]; left[person] -= Math.min(m, left[person]); if (left[person] > 0) line.push(person); // 더 필요하면 맨 뒤로 else order.push(person + 1);}console.log(order.join(" "));import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.StringJoiner;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int[] left = new int[n]; ArrayDeque<Integer> line = new ArrayDeque<>(); st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) { left[i] = Integer.parseInt(st.nextToken()); line.addLast(i); } StringJoiner order = new StringJoiner(" "); while (!line.isEmpty()) { int person = line.pollFirst(); left[person] -= Math.min(m, left[person]); if (left[person] > 0) line.addLast(person); // 더 필요하면 맨 뒤로 else order.add(String.valueOf(person + 1)); } System.out.println(order); }}using System;using System.Collections.Generic;using System.Linq; class Program{ static void Main() { int m = int.Parse(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries)[1]); int[] left = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); var line = new Queue<int>(Enumerable.Range(0, left.Length)); var order = new List<int>(); while (line.Count > 0) { int person = line.Dequeue(); left[person] -= Math.Min(m, left[person]); if (left[person] > 0) line.Enqueue(person); // 더 필요하면 맨 뒤로 else order.Add(person + 1); } Console.WriteLine(string.Join(" ", order)); }}#include <algorithm>#include <iostream>#include <queue>#include <vector> int main() { int n, m; std::cin >> n >> m; std::vector<int> left(n); std::queue<int> line; for (int i = 0; i < n; i++) { std::cin >> left[i]; line.push(i); } bool first = true; while (!line.empty()) { int person = line.front(); line.pop(); left[person] -= std::min(m, left[person]); if (left[person] > 0) { line.push(person); // 더 필요하면 맨 뒤로 } else { std::cout << (first ? "" : " ") << person + 1; first = false; } } std::cout << "\n";}#include <stdio.h> #define MAXN 1000 /* 크기 MAXN인 원형 큐: 줄에는 많아야 n명만 있다 */static int queue[MAXN];static int left[MAXN]; int main(void) { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) { scanf("%d", &left[i]); queue[i] = i; } int head = 0, size = n, printed = 0; while (size > 0) { int person = queue[head]; head = (head + 1) % MAXN; size--; left[person] -= left[person] < m ? left[person] : m; if (left[person] > 0) { queue[(head + size) % MAXN] = person; /* 더 필요하면 맨 뒤로 */ size++; } else { printf(printed++ ? " %d" : "%d", person + 1); } } putchar('\n'); return 0;}첫줄 = 콘솔.수들읽기();n = 첫줄[0];m = 첫줄[1];left = 콘솔.수들읽기(); // 원형 큐: 줄에는 많아야 n명이라 n칸이면 된다. head는 맨 앞 자리, size는 줄 길이.line = 새목록(n, 0);반복 (i = 0; i < n; i++){ line[i] = i;}head = 0;size = n;order = [];동안 (size > 0){ person = line[head]; head = (head + 1) % n; size -= 1; left[person] -= 수학.작은수(m, left[person]); 만약 (left[person] > 0) { // 더 필요하면 맨 뒤로 line[(head + size) % n] = person; size += 1; } 아니면 { order.넣기(person + 1); }}콘솔.쓰기(order);