목록 뒤집기자리 바꾸기P0208

단체 사진 줄 세우기 앞뒤로 넘기기

사진사가 학생 n명을 한 줄로 세워 단체 사진을 찍는다.
학생마다 반 번호가 있고, 같은 반 학생끼리 자리를 바꿔도 같은 줄 세우기로 친다. 그래서 줄 세우기는 반 번호를 늘어놓은 수열 하나로 나타낸다. 가능한 줄 세우기를 모두 사전 순서로 늘어놓는다.
두 줄 세우기를 앞에서부터 견주어 처음으로 다른 자리에서 번호가 작은 쪽이 앞이다. 이 순서는 고리처럼 이어진다.
가장 마지막 줄 세우기(번호가 줄곧 크지 않아지는 것)의 다음은 가장 처음 줄 세우기(번호가 줄곧 작지 않아지는 것)이고, 가장 처음 줄 세우기의 앞은 가장 마지막 줄 세우기다. 지금 줄 세우기에서 m이 양수이면 바로 다음 줄 세우기로 m번 넘어가고, m이 음수이면 바로 앞 줄 세우기로 −m번 되돌아간다.
m이 0이면 그대로다. 그렇게 해서 닿는 줄 세우기를 출력하라. 바로 다음 줄 세우기와 바로 앞 줄 세우기를 구하는 일은 각각 함수로 만들고, 수열 하나를 제자리에서 바꾸게 한다.

입력: 첫 줄에 T(1 ≤ T ≤ 10).
그다음 줄 세우기마다 두 줄: 첫 줄에 n과 m(1 ≤ n ≤ 1000, −200 ≤ m ≤ 200), 둘째 줄에 반 번호 n개(1 ≤ 번호 ≤ 100)
출력: 줄 세우기마다 한 줄: 넘어가거나 되돌아간 뒤의 반 번호 n개를 빈칸 하나로 띄워 출력

예시 1 · stdin

stdout

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

입력(stdin)

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

$ 준비됐어요

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

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

바로 다음 줄 세우기는 세 걸음이에요.
뒤에서부터 보며 처음으로 a[i] < a[i+1]인 i를 찾고, 그 뒤에서 a[i]보다 큰 수 가운데 가장 뒤의 a[j]와 바꾼 다음, i+1부터 끝까지를 뒤집어요.
바꾼 뒤의 뒤쪽은 늘 내림차순이라, 정렬하지 않고 뒤집기만 해도 가장 작은 꼴이 돼요.
i가 없으면(모두 내려가면) 마지막 줄 세우기라 전체를 뒤집으면 첫 줄 세우기예요.
바로 앞 줄 세우기는 비교를 모두 거꾸로 해요.
처음으로 a[i] > a[i+1]인 i를 찾고, 그 뒤에서 a[i]보다 작은 수 가운데 가장 뒤의 것과 바꾼 다음 뒤쪽을 뒤집어요.
i가 없으면(모두 오르면) 첫 줄 세우기라 전체를 뒤집으면 마지막이에요.
언어마다 '일부만 뒤집기'가 달라요.
C++ std::reverse(a.begin() + i + 1, a.end())는 반열린 구간이고, 표준 라이브러리 std::next_permutation·std::prev_permutation이 이 일을 통째로 해 줘요(끝에 닿으면 반대쪽 끝으로 바꾸고 false를 돌려줘요).
C# Array.Reverse(a, 시작, 개수)의 셋째 값은 개수라서 끝 자리를 주면 범위를 넘어 ArgumentException이 나요.
Java는 Collections.reverse(list.subList(i + 1, n))가 원래 목록을 뒤집지만 int[]에는 없어서 두 끝을 바꾸며 좁혀 와요.
C도 그렇게 해요.
크레이콘 목록.뒤집기()는 목록 전체만 뒤집어서, 구간은 두 끝을 바꾸는 동안 반복으로 뒤집어요.
함정 여섯: ① Python a[i + 1:].reverse()와 JS·TS a.slice(i + 1).reverse()는 복사본을 뒤집어서 원래 a는 그대로예요.
Python은 a[i + 1:] = a[i + 1:][::-1]처럼 다시 넣어요.
② 오르는 곳을 a[i] > a[i+1]로 끊으면 같은 번호(2 2)를 오른다고 봐서, 반 번호가 겹칠 때 줄 세우기를 건너뛰거나 되풀이해요.
같으면 계속 왼쪽으로 가야 해요(>=).
앞 줄 세우기에서도 같으면 계속 가야 해요(<=).
③ 바꿀 수를 i 바로 뒤부터 끝 쪽으로 찾으면 '가장 조금 큰 수'가 아니라 처음 만난 큰 수와 바꿔서 여러 줄 세우기를 건너뛰어요.
④ 마지막 줄 세우기에서 아무것도 안 하면 처음으로 돌아가지 않아요.
⑤ 앞 줄 세우기를 다음 줄 세우기에서 베끼며 '큰 수와 바꾸기'를 그대로 두면 엉뚱한 줄이 돼요.
⑥ for (k = 0; k < m; k++)만 쓰면 m이 음수일 때 한 번도 돌지 않아요.

Pythonmain.py · 38 줄

def next_lineup(a):    """a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로)."""    i = len(a) - 2    while i >= 0 and a[i] >= a[i + 1]:  # 뒤에서부터 처음으로 오르는 곳        i -= 1    if i < 0:  # 모두 내려가면 마지막 줄 세우기 → 뒤집으면 첫 줄 세우기        a.reverse()        return    j = len(a) - 1    while a[j] <= a[i]:  # a[i]보다 큰 수 가운데 가장 뒤의 것        j -= 1    a[i], a[j] = a[j], a[i]    a[i + 1:] = a[i + 1:][::-1]  # 뒤쪽 구간만 제자리에서 뒤집는다  def prev_lineup(a):    """a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다."""    i = len(a) - 2    while i >= 0 and a[i] <= a[i + 1]:  # 뒤에서부터 처음으로 내려가는 곳        i -= 1    if i < 0:  # 모두 오르면 첫 줄 세우기 → 뒤집으면 마지막 줄 세우기        a.reverse()        return    j = len(a) - 1    while a[j] >= a[i]:  # a[i]보다 작은 수 가운데 가장 뒤의 것        j -= 1    a[i], a[j] = a[j], a[i]    a[i + 1:] = a[i + 1:][::-1]  t = int(input())for _ in range(t):    n, m = map(int, input().split())    a = list(map(int, input().split()))    step = next_lineup if m > 0 else prev_lineup  # m이 음수면 |m|번 앞으로    for _ in range(abs(m)):        step(a)    print(*a)

JavaScriptmain.js · 48 줄

const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // 구간 [lo, hi]를 제자리에서 뒤집는다function reverseRange(a, lo, hi) {  for (; lo < hi; lo++, hi--) [a[lo], a[hi]] = [a[hi], a[lo]];} // a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로)function nextLineup(a) {  let i = a.length - 2;  while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳  if (i < 0) {    a.reverse(); // 모두 내려가면 마지막 → 뒤집으면 첫 줄 세우기    return;  }  let j = a.length - 1;  while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것  [a[i], a[j]] = [a[j], a[i]];  reverseRange(a, i + 1, a.length - 1);} // a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다function prevLineup(a) {  let i = a.length - 2;  while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳  if (i < 0) {    a.reverse(); // 모두 오르면 첫 줄 세우기 → 뒤집으면 마지막    return;  }  let j = a.length - 1;  while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것  [a[i], a[j]] = [a[j], a[i]];  reverseRange(a, i + 1, a.length - 1);} let p = 0;const t = data[p++];const out = [];for (let c = 0; c < t; c++) {  const n = data[p++];  const m = data[p++];  const a = data.slice(p, p + n);  p += n;  const step = m > 0 ? nextLineup : prevLineup; // m이 음수면 |m|번 앞으로  for (let k = 0; k < Math.abs(m); k++) step(a);  out.push(a.join(" "));}console.log(out.join("\n"));

TypeScriptmain.ts · 49 줄

import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // 구간 [lo, hi]를 제자리에서 뒤집는다function reverseRange(a: number[], lo: number, hi: number): void {  for (; lo < hi; lo++, hi--) [a[lo], a[hi]] = [a[hi], a[lo]];} // a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로)function nextLineup(a: number[]): void {  let i = a.length - 2;  while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳  if (i < 0) {    a.reverse(); // 모두 내려가면 마지막 → 뒤집으면 첫 줄 세우기    return;  }  let j = a.length - 1;  while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것  [a[i], a[j]] = [a[j], a[i]];  reverseRange(a, i + 1, a.length - 1);} // a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다function prevLineup(a: number[]): void {  let i = a.length - 2;  while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳  if (i < 0) {    a.reverse(); // 모두 오르면 첫 줄 세우기 → 뒤집으면 마지막    return;  }  let j = a.length - 1;  while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것  [a[i], a[j]] = [a[j], a[i]];  reverseRange(a, i + 1, a.length - 1);} let p = 0;const t = data[p++];const out: string[] = [];for (let c = 0; c < t; c++) {  const n = data[p++];  const m = data[p++];  const a = data.slice(p, p + n);  p += n;  const step = m > 0 ? nextLineup : prevLineup; // m이 음수면 |m|번 앞으로  for (let k = 0; k < Math.abs(m); k++) step(a);  out.push(a.join(" "));}console.log(out.join("\n"));

JavaMain.java · 64 줄

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main {    static void swap(int[] a, int x, int y) {        int tmp = a[x];        a[x] = a[y];        a[y] = tmp;    }     // 구간 [lo, hi]를 제자리에서 뒤집는다    static void reverseRange(int[] a, int lo, int hi) {        for (; lo < hi; lo++, hi--) swap(a, lo, hi);    }     // a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로)    static void nextLineup(int[] a) {        int i = a.length - 2;        while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳        if (i < 0) {            reverseRange(a, 0, a.length - 1); // 마지막 → 뒤집으면 첫 줄 세우기            return;        }        int j = a.length - 1;        while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것        swap(a, i, j);        reverseRange(a, i + 1, a.length - 1);    }     // a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다    static void prevLineup(int[] a) {        int i = a.length - 2;        while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳        if (i < 0) {            reverseRange(a, 0, a.length - 1); // 첫 줄 세우기 → 뒤집으면 마지막            return;        }        int j = a.length - 1;        while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것        swap(a, i, j);        reverseRange(a, i + 1, a.length - 1);    }     public static void main(String[] args) throws IOException {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        int t = Integer.parseInt(in.readLine().trim());        StringBuilder out = new StringBuilder();        for (int c = 0; c < t; c++) {            StringTokenizer st = new StringTokenizer(in.readLine());            int n = Integer.parseInt(st.nextToken());            int m = Integer.parseInt(st.nextToken());            int[] a = new int[n];            st = new StringTokenizer(in.readLine());            for (int k = 0; k < n; k++) a[k] = Integer.parseInt(st.nextToken());            for (int k = 0; k < m; k++) nextLineup(a);            for (int k = 0; k < -m; k++) prevLineup(a); // m이 음수면 |m|번 앞으로            for (int k = 0; k < n; k++) out.append(k > 0 ? " " : "").append(a[k]);            out.append('\n');        }        System.out.print(out);    }}

C#Main.cs · 55 줄

using System;using System.Linq;using System.Text; class Program{    // a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로)    static void NextLineup(int[] a)    {        int i = a.Length - 2;        while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳        if (i < 0)        {            Array.Reverse(a); // 마지막 → 뒤집으면 첫 줄 세우기            return;        }        int j = a.Length - 1;        while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것        (a[i], a[j]) = (a[j], a[i]);        // Array.Reverse(배열, 시작, 개수) — 셋째 값은 끝 자리가 아니라 개수다        Array.Reverse(a, i + 1, a.Length - (i + 1));    }     // a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다    static void PrevLineup(int[] a)    {        int i = a.Length - 2;        while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳        if (i < 0)        {            Array.Reverse(a); // 첫 줄 세우기 → 뒤집으면 마지막            return;        }        int j = a.Length - 1;        while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것        (a[i], a[j]) = (a[j], a[i]);        Array.Reverse(a, i + 1, a.Length - (i + 1));    }     static void Main()    {        int t = int.Parse(Console.ReadLine()!.Trim());        var output = new StringBuilder();        for (int c = 0; c < t; c++)        {            int[] nm = Console.ReadLine()!.Trim().Split(' ').Select(int.Parse).ToArray();            int[] a = Console.ReadLine()!.Trim().Split(' ').Select(int.Parse).ToArray();            int m = nm[1];            for (int k = 0; k < m; k++) NextLineup(a);            for (int k = 0; k < -m; k++) PrevLineup(a); // m이 음수면 |m|번 앞으로            output.Append(string.Join(" ", a)).Append('\n');        }        Console.Write(output);    }}

C++main.cpp · 49 줄

#include <algorithm>#include <iostream>#include <vector> // a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로)// (표준 라이브러리 std::next_permutation이 바로 이 일을 한다 — 여기서는 직접 쓴다)void nextLineup(std::vector<int>& a) {    int i = (int)a.size() - 2;    while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳    if (i < 0) {        std::reverse(a.begin(), a.end()); // 마지막 → 뒤집으면 첫 줄 세우기        return;    }    int j = (int)a.size() - 1;    while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것    std::swap(a[i], a[j]);    std::reverse(a.begin() + i + 1, a.end()); // [시작, 끝) 반열린 구간} // a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다// (std::prev_permutation이 이 일을 한다)void prevLineup(std::vector<int>& a) {    int i = (int)a.size() - 2;    while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳    if (i < 0) {        std::reverse(a.begin(), a.end()); // 첫 줄 세우기 → 뒤집으면 마지막        return;    }    int j = (int)a.size() - 1;    while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것    std::swap(a[i], a[j]);    std::reverse(a.begin() + i + 1, a.end());} int main() {    std::ios::sync_with_stdio(false);    int t;    std::cin >> t;    while (t--) {        int n, m;        std::cin >> n >> m;        std::vector<int> a(n);        for (int& x : a) std::cin >> x;        for (int k = 0; k < m; k++) nextLineup(a);        for (int k = 0; k < -m; k++) prevLineup(a); // m이 음수면 |m|번 앞으로        for (int k = 0; k < n; k++) std::cout << (k ? " " : "") << a[k];        std::cout << '\n';    }}

Cmain.c · 56 줄

#include <stdio.h> static void swap(int *x, int *y) {    int tmp = *x;    *x = *y;    *y = tmp;} /* 구간 [lo, hi]를 제자리에서 뒤집는다 */static void reverse_range(int *a, int lo, int hi) {    for (; lo < hi; lo++, hi--) swap(&a[lo], &a[hi]);} /* a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로) */static void next_lineup(int *a, int n) {    int i = n - 2;    while (i >= 0 && a[i] >= a[i + 1]) i--; /* 뒤에서부터 처음으로 오르는 곳 */    if (i < 0) {        reverse_range(a, 0, n - 1); /* 마지막 → 뒤집으면 첫 줄 세우기 */        return;    }    int j = n - 1;    while (a[j] <= a[i]) j--; /* a[i]보다 큰 수 가운데 가장 뒤의 것 */    swap(&a[i], &a[j]);    reverse_range(a, i + 1, n - 1);} /* a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다 */static void prev_lineup(int *a, int n) {    int i = n - 2;    while (i >= 0 && a[i] <= a[i + 1]) i--; /* 뒤에서부터 처음으로 내려가는 곳 */    if (i < 0) {        reverse_range(a, 0, n - 1); /* 첫 줄 세우기 → 뒤집으면 마지막 */        return;    }    int j = n - 1;    while (a[j] >= a[i]) j--; /* a[i]보다 작은 수 가운데 가장 뒤의 것 */    swap(&a[i], &a[j]);    reverse_range(a, i + 1, n - 1);} int main(void) {    int t;    scanf("%d", &t);    static int a[1000];    while (t--) {        int n, m;        scanf("%d %d", &n, &m);        for (int k = 0; k < n; k++) scanf("%d", &a[k]);        for (int k = 0; k < m; k++) next_lineup(a, n);        for (int k = 0; k < -m; k++) prev_lineup(a, n); /* m이 음수면 |m|번 앞으로 */        for (int k = 0; k < n; k++) printf(k ? " %d" : "%d", a[k]);        printf("\n");    }    return 0;}

Craykonmain.cray · 77 줄

// 구간 [lo, hi]를 제자리에서 뒤집는다(목록.뒤집기()는 목록 전체만 뒤집는다)구간뒤집기(a, lo, hi){    동안 (lo < hi)    {        tmp = a[lo];        a[lo] = a[hi];        a[hi] = tmp;        lo += 1;        hi -= 1;    }} // a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로)다음줄(a){    i = a.개수 - 2;    동안 (i >= 0 && a[i] >= a[i + 1])    {        i -= 1;    }    만약 (i < 0)    {        a.뒤집기(); // 마지막 → 뒤집으면 첫 줄 세우기        돌려주기;    }    j = a.개수 - 1;    동안 (a[j] <= a[i])    {        j -= 1;    }    tmp = a[i];    a[i] = a[j];    a[j] = tmp;    구간뒤집기(a, i + 1, a.개수 - 1);} // a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다앞줄(a){    i = a.개수 - 2;    동안 (i >= 0 && a[i] <= a[i + 1])    {        i -= 1;    }    만약 (i < 0)    {        a.뒤집기(); // 첫 줄 세우기 → 뒤집으면 마지막        돌려주기;    }    j = a.개수 - 1;    동안 (a[j] >= a[i])    {        j -= 1;    }    tmp = a[i];    a[i] = a[j];    a[j] = tmp;    구간뒤집기(a, i + 1, a.개수 - 1);} t = 콘솔.줄읽기().공백제거().수로변환();반복 (c = 0; c < t; c++){    nm = 콘솔.수들읽기();    a = 콘솔.수들읽기();    m = nm[1];    반복 (k = 0; k < m; k++)    {        다음줄(a);    }    반복 (k = 0; k < -m; k++)    {        앞줄(a);    }    콘솔.쓰기(a.잇기(" "));}