물류 창고의 띠 위에 번호표가 붙은 상자 n개가 한 줄로 놓여 있었다.
로봇이 작업 q개를 차례대로 했고, 지금은 작업 기록과 작업을 모두 마친 뒤의 줄만 남아 있다.
자리는 그 작업을 할 때의 줄에서 맨 앞 상자를 1로 하여 센다.
S i j는 i번째 상자와 j번째 상자를 맞바꾼 작업이다.
M i j는 i번째 상자를 꺼낸 다음(뒤의 상자들은 한 칸씩 앞으로 당겨진다), 그 상자가 새 줄의 j번째가 되도록 끼워 넣은 작업이다.
L k는 맨 앞 상자를 떼어 맨 뒤에 놓는 일을 k번 한 작업이다.
F i j는 i번째부터 j번째까지의 상자를 그 자리에서 거꾸로 뒤집은 작업이다.
첫 줄에 n과 q가 주어진다.
둘째 줄에 작업을 모두 마친 뒤의 줄이 맨 앞 상자부터 번호표 n개로 주어진다.
다음 q줄에 작업이 한 줄에 하나씩, 로봇이 한 차례대로 주어진다.
마지막 줄에 정수 t가 주어진다.
한 줄 안의 값은 빈칸 하나로 띄운다.
첫 줄에 t번째 작업을 하기 바로 전의 줄을, 둘째 줄에 첫 작업을 하기 전의 처음 줄을 출력하라.
줄은 맨 앞 상자부터 번호표를 빈칸 하나로 띄워 쓴다.
기록을 마지막 작업부터 첫 작업까지 거꾸로 돌며, 작업마다 그 작업을 되돌리는 일을 하면 된다.
입력
1 ≤ n ≤ 1,000. 1 ≤ q ≤ 2,000. 번호표는 1 이상 1,000,000 이하의 정수이고(쉼표 없이 숫자만 주어진다) 같은 번호표가 여러 개 있을 수 있다. S와 M은 1 ≤ i ≤ n, 1 ≤ j ≤ n(i와 j가 같을 수 있다). F는 1 ≤ i ≤ j ≤ n. L은 1 ≤ k ≤ n. 1 ≤ t ≤ q
출력
두 줄. 첫 줄은 t번째 작업 바로 전의 줄, 둘째 줄은 처음 줄(번호표 n개씩)
예시 1 · stdin
5 4
30 20 50 10 40
M 1 4
L 2
S 1 5
F 2 4
3
stdout
40 10 50 20 30
10 20 30 40 50
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
거꾸로 도는 반복문은 언어마다 달라요. Python은 for idx in range(q - 1, -1, -1)인데, 끝 값은 들어가지 않으므로 0번까지 돌려면 끝을 -1로 적어요. range(q - 1, 0, -1)이라 쓰면 첫 작업을 빠뜨려요. JS·TS·Java·C#·C·C++는 for (int idx = q - 1; idx >= 0; idx--), 크레이콘은 반복 (idx = q - 1; idx >= 0; idx--)예요. 시작을 q로, 조건을 idx > 0으로 적으면 없는 q번 칸을 읽고 0번 칸을 빠뜨려요. C·C++에서 번호를 unsigned나 size_t로 두면 0에서 1을 뺀 값이 아주 큰 수가 되어 idx >= 0이 늘 참이라 반복이 끝나지 않고 배열 밖을 읽게 돼요. C++ ops.at(idx)는 그때 예외를 던져 멈추지만, ops[idx]나 C 배열은 무슨 일이 일어날지 정해져 있지 않아요. 목록을 뒤집어 놓고 앞에서부터 돌 수도 있어요. Python reversed(ops)는 뒤집어 도는 것을 돌려주지만 ops.reverse()는 제자리에서 뒤집고 None을 돌려줘서 for op in ops.reverse()는 TypeError예요. JS ops.reverse()는 제자리에서 뒤집고 그 배열을 돌려줘요. C++는 rbegin()부터 rend()까지 돌 수 있어요. 순서만 거꾸로 해서는 안 되고 작업마다 반대 일을 해야 해요. 예시에서 기록을 앞에서부터 되돌리면 처음 줄이 20 30 10 40 50으로 틀려요. S와 F는 한 번 더 하면 되돌아가지만, M i j는 j번째에서 꺼내 i번째에 끼워야 하고(Python row.insert(i - 1, row.pop(j - 1)), 크레이콘 자리빼기와 끼우기), L k는 맨 뒤 k개를 맨 앞으로 가져와야 해요(Python row[n - k:] + row[:n - k], Java Collections.rotate(row, k), C++ std::rotate). 마지막으로 't번째 작업 바로 전'은 t번째 작업을 되돌린 바로 뒤예요. 0부터 세면 그 작업은 t - 1번이라 idx == t - 1일 때 써요. idx == t일 때 쓰면 t번째 작업을 한 뒤의 줄이 나오고, t가 q이면 그 줄이 아예 안 나와요.
Pythonmain.py · 28 줄
import syslines = sys.stdin.read().split("\n")n, q = map(int, lines[0].split())row = lines[1].split()ops = [lines[2 + i].split() for i in range(q)]t = int(lines[2 + q])out = []# 마지막 작업부터 첫 작업까지 거꾸로: range의 끝 -1은 들어가지 않으므로 0번까지 돈다for idx in range(q - 1, -1, -1): op = ops[idx] a = int(op[1]) if op[0] == "S": # 맞바꾸기는 한 번 더 하면 되돌아간다 b = int(op[2]) row[a - 1], row[b - 1] = row[b - 1], row[a - 1] elif op[0] == "M": # i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 b = int(op[2]) row.insert(a - 1, row.pop(b - 1)) elif op[0] == "L": # 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 row = row[n - a:] + row[:n - a] else: # F: 뒤집기도 한 번 더 하면 되돌아간다 b = int(op[2]) row[a - 1:b] = row[a - 1:b][::-1] if idx == t - 1: # t번 작업을 되돌린 직후 = t번 작업을 하기 직전 out.append(" ".join(row))out.append(" ".join(row))print("\n".join(out))
JavaScriptmain.js · 29 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(/\s+/).map(Number);let row = lines[1].trim().split(/\s+/);const ops = [];for (let i = 0; i < q; i++) ops.push(lines[2 + i].trim().split(/\s+/));const t = Number(lines[2 + q]);const out = [];// 마지막 작업부터 첫 작업까지 거꾸로for (let idx = q - 1; idx >= 0; idx--) { const op = ops[idx]; const a = Number(op[1]); const b = Number(op[2]); if (op[0] === "S") { [row[a - 1], row[b - 1]] = [row[b - 1], row[a - 1]]; } else if (op[0] === "M") { // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 const [box] = row.splice(b - 1, 1); row.splice(a - 1, 0, box); } else if (op[0] === "L") { // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 row = row.slice(n - a).concat(row.slice(0, n - a)); } else { for (let l = a - 1, r = b - 1; l < r; l++, r--) [row[l], row[r]] = [row[r], row[l]]; } if (idx === t - 1) out.push(row.join(" ")); // t번 작업을 하기 직전}out.push(row.join(" "));console.log(out.join("\n"));
TypeScriptmain.ts · 31 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(/\s+/).map(Number);let row: string[] = lines[1].trim().split(/\s+/);const ops: string[][] = [];for (let i = 0; i < q; i++) ops.push(lines[2 + i].trim().split(/\s+/));const t: number = Number(lines[2 + q]);const out: string[] = [];// 마지막 작업부터 첫 작업까지 거꾸로for (let idx = q - 1; idx >= 0; idx--) { const op = ops[idx]; const a = Number(op[1]); const b = Number(op[2]); if (op[0] === "S") { [row[a - 1], row[b - 1]] = [row[b - 1], row[a - 1]]; } else if (op[0] === "M") { // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 const [box] = row.splice(b - 1, 1); row.splice(a - 1, 0, box); } else if (op[0] === "L") { // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 row = row.slice(n - a).concat(row.slice(0, n - a)); } else { for (let l = a - 1, r = b - 1; l < r; l++, r--) [row[l], row[r]] = [row[r], row[l]]; } if (idx === t - 1) out.push(row.join(" ")); // t번 작업을 하기 직전}out.push(row.join(" "));console.log(out.join("\n"));
JavaMain.java · 42 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] head = in.readLine().trim().split("\\s+"); int n = Integer.parseInt(head[0]), q = Integer.parseInt(head[1]); List<String> row = new ArrayList<>(Arrays.asList(in.readLine().trim().split("\\s+"))); String[][] ops = new String[q][]; for (int i = 0; i < q; i++) ops[i] = in.readLine().trim().split("\\s+"); int t = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); // 마지막 작업부터 첫 작업까지 거꾸로 for (int idx = q - 1; idx >= 0; idx--) { String[] op = ops[idx]; int a = Integer.parseInt(op[1]); switch (op[0]) { case "S": Collections.swap(row, a - 1, Integer.parseInt(op[2]) - 1); break; case "M": // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 row.add(a - 1, row.remove(Integer.parseInt(op[2]) - 1)); break; case "L": // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 Collections.rotate(row, a); break; default: Collections.reverse(row.subList(a - 1, Integer.parseInt(op[2]))); } if (idx == t - 1) out.append(String.join(" ", row)).append('\n'); // t번 작업을 하기 직전 } out.append(String.join(" ", row)).append('\n'); System.out.print(out); }}
C#Main.cs · 57 줄
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] head = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(head[0]), q = int.Parse(head[1]); var row = new List<string>(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries)); var ops = new string[q][]; for (int i = 0; i < q; i++) ops[i] = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int t = int.Parse(Console.ReadLine()); var sb = new StringBuilder(); // 마지막 작업부터 첫 작업까지 거꾸로 for (int idx = q - 1; idx >= 0; idx--) { string[] op = ops[idx]; int a = int.Parse(op[1]); switch (op[0]) { case "S": { int b = int.Parse(op[2]); (row[a - 1], row[b - 1]) = (row[b - 1], row[a - 1]); break; } case "M": // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 { int b = int.Parse(op[2]); string box = row[b - 1]; row.RemoveAt(b - 1); row.Insert(a - 1, box); break; } case "L": // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 { List<string> tail = row.GetRange(n - a, a); row.RemoveRange(n - a, a); row.InsertRange(0, tail); break; } default: { int b = int.Parse(op[2]); row.Reverse(a - 1, b - a + 1); // (시작 자리, 개수) break; } } if (idx == t - 1) sb.Append(string.Join(" ", row)).Append('\n'); // t번 작업을 하기 직전 } sb.Append(string.Join(" ", row)).Append('\n'); Console.Write(sb); }}
C++main.cpp · 49 줄
#include <algorithm>#include <iostream>#include <vector>struct Op { char kind; int a, b;};static void printRow(const std::vector<int>& row) { for (size_t i = 0; i < row.size(); i++) std::cout << (i ? " " : "") << row[i]; std::cout << '\n';}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q, t; std::cin >> n >> q; std::vector<int> row(n); for (int& x : row) std::cin >> x; std::vector<Op> ops(q); for (Op& op : ops) { std::cin >> op.kind >> op.a; op.b = 0; if (op.kind != 'L') std::cin >> op.b; } std::cin >> t; // 마지막 작업부터 첫 작업까지 거꾸로 for (int idx = q - 1; idx >= 0; idx--) { const Op& op = ops[idx]; if (op.kind == 'S') { std::swap(row[op.a - 1], row[op.b - 1]); } else if (op.kind == 'M') { // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 int box = row[op.b - 1]; row.erase(row.begin() + (op.b - 1)); row.insert(row.begin() + (op.a - 1), box); } else if (op.kind == 'L') { // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 std::rotate(row.begin(), row.end() - op.a, row.end()); } else { std::reverse(row.begin() + (op.a - 1), row.begin() + op.b); } if (idx == t - 1) printRow(row); // t번 작업을 하기 직전 } printRow(row);}
Cmain.c · 56 줄
#include <stdio.h>#include <string.h>#define MAXN 1000#define MAXQ 2000static int row[MAXN], tmp[MAXN];static char kind[MAXQ];static int pa[MAXQ], pb[MAXQ];static void print_row(int n) { for (int i = 0; i < n; i++) printf(i ? " %d" : "%d", row[i]); putchar('\n');}int main(void) { int n, q, t; scanf("%d %d", &n, &q); for (int i = 0; i < n; i++) scanf("%d", &row[i]); for (int i = 0; i < q; i++) { scanf(" %c %d", &kind[i], &pa[i]); pb[i] = 0; if (kind[i] != 'L') scanf("%d", &pb[i]); } scanf("%d", &t); /* 마지막 작업부터 첫 작업까지 거꾸로 */ for (int idx = q - 1; idx >= 0; idx--) { int a = pa[idx], b = pb[idx]; if (kind[idx] == 'S') { int x = row[a - 1]; row[a - 1] = row[b - 1]; row[b - 1] = x; } else if (kind[idx] == 'M') { /* i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 */ int box = row[b - 1]; if (b < a) memmove(&row[b - 1], &row[b], (size_t)(a - b) * sizeof(int)); else memmove(&row[a], &row[a - 1], (size_t)(b - a) * sizeof(int)); row[a - 1] = box; } else if (kind[idx] == 'L') { /* 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 */ memcpy(tmp, &row[n - a], (size_t)a * sizeof(int)); memcpy(tmp + a, row, (size_t)(n - a) * sizeof(int)); memcpy(row, tmp, (size_t)n * sizeof(int)); } else { for (int l = a - 1, r = b - 1; l < r; l++, r--) { int x = row[l]; row[l] = row[r]; row[r] = x; } } if (idx == t - 1) print_row(n); /* t번 작업을 하기 직전 */ } print_row(n); return 0;}
Craykonmain.cray · 60 줄
head = 콘솔.수들읽기();n = head[0];q = head[1];row = 콘솔.수들읽기();ops = [];반복 (i = 0; i < q; i++){ ops.넣기(콘솔.줄읽기().공백제거().나누기(" "));}t = 콘솔.줄읽기().수로변환();// 마지막 작업부터 첫 작업까지 거꾸로반복 (idx = q - 1; idx >= 0; idx--){ op = ops[idx]; a = op[1].수로변환(); 선택 (op[0]) { 경우 "S": b = op[2].수로변환(); x = row[a - 1]; row[a - 1] = row[b - 1]; row[b - 1] = x; 그만; 경우 "M": // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 b = op[2].수로변환(); box = row[b - 1]; row.자리빼기(b - 1); row.끼우기(a - 1, box); 그만; 경우 "L": // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 앞 = row.부분목록(0, n - a); row = row.부분목록(n - a, a); 각각 (v 에서 앞) { row.넣기(v); } 그만; 그밖에: l = a - 1; r = op[2].수로변환() - 1; 동안 (l < r) { x = row[l]; row[l] = row[r]; row[r] = x; l++; r--; } 그만; } 만약 (idx == t - 1) { // t번 작업을 하기 직전 콘솔.쓰기(row.잇기(" ")); }}콘솔.쓰기(row.잇기(" "));