자리 바꾸기목록 정렬목록 자르기P0177

창고 선반 구간 정리

창고 선반 한 줄에 상자 n개가 놓여 있고, 칸 번호는 왼쪽부터 1, 2, …, n이다. 둘째 줄에 칸 순서대로 상자 무게 n개가 주어진다. 셋째 줄에 명령 수 q가, 다음 q줄에 명령이 하나씩 주어진다. 명령은 세 가지이다. "swap i j"는 i번 칸과 j번 칸의 상자를 맞바꾼다(i와 j가 같으면 그대로이고, i가 j보다 클 수도 있다). "sort l r"는 l번 칸부터 r번 칸까지(양 끝 포함)의 상자만 가벼운 것이 왼쪽에 오도록 늘어놓는다. 이 구간 밖의 상자는 움직이지 않는다. "show l r"는 지금 l번 칸부터 r번 칸까지(양 끝 포함)의 무게를 빈칸 하나씩 띄워 한 줄에 출력한다. show 명령마다 한 줄씩, 명령 순서대로 출력하라.

입력: 1 ≤ n ≤ 1000, 1 ≤ q ≤ 1000, 1 ≤ 무게 ≤ 1,000,000(정수).
swap은 1 ≤ i, j ≤ n, sort·show는 1 ≤ l ≤ r ≤ n.
show 명령은 적어도 하나 있고, show로 출력하는 무게는 모두 합쳐 20,000개 이하
출력: show 명령마다 한 줄

예시 1 · stdin

6
30 4 100 25 9 7
5
sort 2 5
show 1 6
swap 1 6
sort 4 6
show 3 5

stdout

30 4 9 25 100 7
9 25 30

예시 2 · stdin

3
5 1 3
4
show 2 2
swap 3 3
sort 1 1
show 1 3

stdout

1
5 1 3

main.py 프로그래밍 언어 실행 판

입력(stdin)

실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).

$ 준비됐어요

코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.

다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이

목록의 한 구간을 자르고 정렬하는 방법이 언어마다 "끝을 넣느냐", "사본이냐 제자리냐"에서 갈려요.
1부터 센 l ~ r(양 끝 포함)을 자르기: Python a[l-1:r], JS·TS a.slice(l-1, r), Java Arrays.copyOfRange(a, l-1, r)(셋 다 끝 자리는 넣지 않아요), C# 범위 a[(l-1)..r](역시 끝은 빼요), 크레이콘 a.부분목록(l-1, r-l+1)(시작과 개수).
구간 정렬: Java Arrays.sort(a, l-1, r)와 C++ std::sort(a.begin()+l-1, a.begin()+r)은 끝을 빼고 제자리에서 정렬하고, C# Array.Sort(a, l-1, r-l+1)과 C qsort(a+l-1, r-l+1, …)는 시작과 개수를 받아요.
함정 하나: Python a[l-1:r].sort()는 잘라 낸 사본을 정렬하고 버려서 선반은 그대로예요.
a[l-1:r] = sorted(a[l-1:r])처럼 다시 넣어야 해요.
크레이콘 부분목록도 새 목록이라 정렬한 뒤 칸마다 다시 써 넣고, JS는 splice로 다시 넣어요.
함정 둘: JS·TS sort()에 비교 함수를 안 주면 수를 문자열로 바꿔 비교해서 [10, 9, 100]이 [10, 100, 9]가 돼요.
sort((u, v) => u - v)를 써요.
함정 셋: C# Array.Sort(a, 시작, 끝)처럼 셋째 값에 끝 자리를 넣으면 개수가 틀려서 구간 밖까지 정렬하거나 오류가 나요.
함정 넷: a[l-1:r-1]처럼 끝을 하나 덜 자르면 r번 칸이 빠져요.
두 칸 맞바꾸기는 Python a[i], a[j] = a[j], a[i], JS·TS 구조 분해, C# 튜플, C++ std::swap, Java·C·크레이콘 임시 변수예요.

Pythonmain.py · 18 줄

import sys lines = sys.stdin.read().split("\n")n = int(lines[0])shelf = list(map(int, lines[1].split()))q = int(lines[2])out = []for line in lines[3:3 + q]:    cmd, a, b = line.split()    a, b = int(a) - 1, int(b)          # 0부터 세는 시작 a, 끝 b(b는 들어가지 않음)    if cmd == "swap":        i, j = a, b - 1        shelf[i], shelf[j] = shelf[j], shelf[i]    elif cmd == "sort":        shelf[a:b] = sorted(shelf[a:b])  # 잘라 낸 것은 사본이라 정렬한 뒤 그 자리에 다시 넣는다    else:        out.append(" ".join(map(str, shelf[a:b])))print("\n".join(out))

JavaScriptmain.js · 19 줄

const lines = require("fs").readFileSync(0, "utf8").split("\n");const shelf = lines[1].trim().split(/\s+/).map(Number);const q = Number(lines[2]);const out = [];for (const line of lines.slice(3, 3 + q)) {  const [cmd, x, y] = line.trim().split(" ");  const a = Number(x) - 1;  const b = Number(y); // slice(a, b)는 b를 넣지 않는다  if (cmd === "swap") {    [shelf[a], shelf[b - 1]] = [shelf[b - 1], shelf[a]];  } else if (cmd === "sort") {    // 비교 함수가 없으면 문자열로 비교해서 "10" < "9"가 된다    const part = shelf.slice(a, b).sort((u, v) => u - v);    shelf.splice(a, part.length, ...part);  } else {    out.push(shelf.slice(a, b).join(" "));  }}console.log(out.join("\n"));

TypeScriptmain.ts · 20 줄

import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const shelf: number[] = lines[1].trim().split(/\s+/).map(Number);const q = Number(lines[2]);const out: string[] = [];for (const line of lines.slice(3, 3 + q)) {  const [cmd, x, y] = line.trim().split(" ");  const a = Number(x) - 1;  const b = Number(y); // slice(a, b)는 b를 넣지 않는다  if (cmd === "swap") {    [shelf[a], shelf[b - 1]] = [shelf[b - 1], shelf[a]];  } else if (cmd === "sort") {    // 비교 함수가 없으면 문자열로 비교해서 "10" < "9"가 된다    const part: number[] = shelf.slice(a, b).sort((u, v) => u - v);    shelf.splice(a, part.length, ...part);  } else {    out.push(shelf.slice(a, b).join(" "));  }}console.log(out.join("\n"));

JavaMain.java · 29 줄

import java.io.*;import java.util.*; public class Main {    public static void main(String[] args) throws IOException {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        int n = Integer.parseInt(br.readLine().trim());        int[] shelf = Arrays.stream(br.readLine().trim().split(" ")).mapToInt(Integer::parseInt).toArray();        int q = Integer.parseInt(br.readLine().trim());        StringBuilder out = new StringBuilder();        for (int k = 0; k < q; k++) {            String[] p = br.readLine().trim().split(" ");            int a = Integer.parseInt(p[1]) - 1;            int b = Integer.parseInt(p[2]); // 끝 자리 b는 들어가지 않는다(toIndex)            if (p[0].equals("swap")) {                int tmp = shelf[a];                shelf[a] = shelf[b - 1];                shelf[b - 1] = tmp;            } else if (p[0].equals("sort")) {                Arrays.sort(shelf, a, b); // 그 구간만 제자리에서 정렬            } else {                StringJoiner sj = new StringJoiner(" ");                for (int w : Arrays.copyOfRange(shelf, a, b)) sj.add(String.valueOf(w));                out.append(sj).append('\n');            }        }        System.out.print(out);    }}

C#Main.cs · 32 줄

using System;using System.Linq;using System.Text; class Program{    static void Main()    {        Console.ReadLine();        int[] shelf = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();        int q = int.Parse(Console.ReadLine().Trim());        var sb = new StringBuilder();        for (int k = 0; k < q; k++)        {            string[] p = Console.ReadLine().Trim().Split(' ');            int a = int.Parse(p[1]) - 1, b = int.Parse(p[2]) - 1; // 둘 다 0부터, b도 들어간다            if (p[0] == "swap")            {                (shelf[a], shelf[b]) = (shelf[b], shelf[a]);            }            else if (p[0] == "sort")            {                Array.Sort(shelf, a, b - a + 1); // (시작, 개수)다. 끝 자리가 아니다            }            else            {                sb.Append(string.Join(" ", shelf[a..(b + 1)])).Append('\n'); // 범위 a..c 는 c를 넣지 않는다            }        }        Console.Write(sb);    }}

C++main.cpp · 29 줄

#include <algorithm>#include <iostream>#include <string>#include <utility>#include <vector> int main() {    std::ios::sync_with_stdio(false);    int n, q;    std::cin >> n;    std::vector<int> shelf(n);    for (int& w : shelf) std::cin >> w;    std::cin >> q;    std::string out;    for (int k = 0; k < q; k++) {        std::string cmd;        int a, b;        std::cin >> cmd >> a >> b;        if (cmd == "swap") {            std::swap(shelf[a - 1], shelf[b - 1]);        } else if (cmd == "sort") {            std::sort(shelf.begin() + (a - 1), shelf.begin() + b); // [첫, 끝) — 끝은 들어가지 않는다        } else {            for (int i = a - 1; i < b; i++) out += (i > a - 1 ? " " : "") + std::to_string(shelf[i]);            out += "\n";        }    }    std::cout << out;}

Cmain.c · 32 줄

#include <stdio.h>#include <stdlib.h> static int ascending(const void* x, const void* y) {    int a = *(const int*)x, b = *(const int*)y;    return (a > b) - (a < b);} int main(void) {    static int shelf[1000];    int n, q;    scanf("%d", &n);    for (int i = 0; i < n; i++) scanf("%d", &shelf[i]);    scanf("%d", &q);    for (int k = 0; k < q; k++) {        char cmd[8];        int a, b;        scanf("%7s %d %d", cmd, &a, &b);        a--, b--; /* 둘 다 0부터 */        if (cmd[1] == 'w') { /* swap */            int tmp = shelf[a];            shelf[a] = shelf[b];            shelf[b] = tmp;        } else if (cmd[1] == 'o') { /* sort: a번부터 (b - a + 1)칸 */            qsort(shelf + a, b - a + 1, sizeof shelf[0], ascending);        } else { /* show */            for (int i = a; i <= b; i++) printf(i > a ? " %d" : "%d", shelf[i]);            printf("\n");        }    }    return 0;}

Craykonmain.cray · 29 줄

n = 콘솔.줄읽기().수로변환();shelf = 콘솔.수들읽기();q = 콘솔.줄읽기().수로변환();반복 (k = 0; k < q; k++){    p = 콘솔.줄읽기().공백제거().나누기();    a = p[1].수로변환() - 1;    b = p[2].수로변환() - 1; // 둘 다 0부터, b도 들어간다    만약 (p[0] == "swap")    {        tmp = shelf[a];        shelf[a] = shelf[b];        shelf[b] = tmp;    }    아니면 만약 (p[0] == "sort")    {        // 부분목록은 (시작, 개수)로 잘라 낸 새 목록이라, 정렬한 뒤 제자리에 다시 써 넣는다        part = shelf.부분목록(a, b - a + 1);        part.정렬();        반복 (i = 0; i < part.개수; i++)        {            shelf[a + i] = part[i];        }    }    아니면    {        콘솔.쓰기(shelf.부분목록(a, b - a + 1).잇기(" "));    }}