교실에 자리가 한 줄로 n개 있고, 자리 번호는 왼쪽부터 1, 2, …, n이다.
첫 줄에 n이, 둘째 줄에 처음 자리에 앉은 학생 이름 n개가 자리 순서대로 빈칸 하나씩 띄워 주어진다.
셋째 줄에 바꾸기 수 m이, 다음 m줄에 바꾸기 "i j"가 한 줄에 하나씩 주어진다. 담임 선생님은 이 바꾸기를 주어진 차례대로 한다.
바꾸기 "i j"는 i번 자리 학생과 j번 자리 학생이 자리를 맞바꾸는 것이다.
i와 j가 같으면 아무 일도 일어나지 않는다.
바꾸기를 모두 마친 뒤, 첫 줄에 자리 순서대로 학생 이름을 빈칸 하나씩 띄워 출력하라.
둘째 줄에는 처음 자리와 마지막 자리가 다른 학생 수 k를 출력하라.
이어서 k줄에 그런 학생마다 "이름 처음자리 마지막자리"를 빈칸 하나씩 띄워 출력하라.
이 k줄은 처음 자리 번호가 작은 학생부터 출력한다.
여러 번 옮겼더라도 마지막에 처음 자리로 돌아온 학생은 세지 않는다.
k가 0이면 둘째 줄의 0까지만 출력한다.
입력
1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000, 1 ≤ i, j ≤ n. 이름은 영어 소문자 1 ~ 10글자이고 모두 다르다
출력
첫 줄에 마지막 자리 순서의 이름, 둘째 줄에 k, 이어서 k줄에 "이름 처음자리 마지막자리"
예시 1 · stdin
5
mina joon sora dan kai
3
1 3
2 5
3 1
stdout
mina kai sora dan joon
2
joon 2 5
kai 5 2
예시 2 · stdin
3
ari bo cy
3
1 2
2 3
3 1
stdout
ari cy bo
2
bo 2 3
cy 3 2
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
처음 자리를 남겨 두려면 바꾸기 전에 목록을 복사해야 해요. 함정 하나: start = seats는 복사가 아니라 같은 목록에 이름을 하나 더 붙이는 것이라, 바꾸기가 두 이름 모두에 보여서 옮긴 학생이 늘 0명으로 나와요. Python·JS·TS·Java·C#의 목록과 배열, 크레이콘 목록이 모두 이렇게 같은 것을 가리켜요. 복사하는 법: Python seats[:]·list(seats), JS·TS [...seats]·slice(), Java seats.clone(), C# (string[])seats.Clone(), 크레이콘 seats.부분목록(0, seats.개수). C++ std::vector만 =가 칸을 통째로 복사하고, C 배열은 =로 대입할 수 없어서 memcpy나 strcpy로 칸마다 옮겨요. 두 칸을 맞바꾸는 법: Python a[i], a[j] = a[j], a[i], JS·TS [a[i], a[j]] = [a[j], a[i]], C# 튜플 (a[i], a[j]) = (a[j], a[i]), C++ std::swap(a[i], a[j])이고, Java·C·크레이콘은 임시 변수 tmp를 써요(C 문자열은 strcpy 세 번). 함정 둘: 임시 변수 없이 a[i] = a[j]; a[j] = a[i];로 쓰면 앞줄에서 a[i]가 이미 덮여서 두 칸이 같은 이름이 돼요. 마지막에 지금 자리를 찾을 때는 이름 → 자리 사전을 한 번 만들면 학생마다 다시 찾지 않아도 돼요.
Pythonmain.py · 19 줄
import sysdata = sys.stdin.read().split()n = int(data[0])seats = data[1:1 + n]start = seats[:] # 처음 자리를 따로 복사해 둔다(start = seats 는 같은 목록에 이름만 둘)m = int(data[1 + n])pos = 2 + nfor _ in range(m): i, j = int(data[pos]) - 1, int(data[pos + 1]) - 1 pos += 2 seats[i], seats[j] = seats[j], seats[i]now = {name: k for k, name in enumerate(seats)}moved = [(name, k + 1, now[name] + 1) for k, name in enumerate(start) if now[name] != k]print(" ".join(seats))print(len(moved))for name, a, b in moved: print(name, a, b)
JavaScriptmain.js · 20 줄
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const n = Number(data[0]);const seats = data.slice(1, 1 + n);const start = [...seats]; // 복사본. const start = seats 는 같은 배열을 가리킨다const m = Number(data[1 + n]);let pos = 2 + n;for (let k = 0; k < m; k++, pos += 2) { const i = Number(data[pos]) - 1; const j = Number(data[pos + 1]) - 1; [seats[i], seats[j]] = [seats[j], seats[i]];}const now = new Map(seats.map((name, k) => [name, k]));const out = [seats.join(" ")];const moved = [];start.forEach((name, k) => { if (now.get(name) !== k) moved.push(`${name} ${k + 1} ${now.get(name) + 1}`);});out.push(String(moved.length), ...moved);console.log(out.join("\n"));
TypeScriptmain.ts · 22 줄
import { readFileSync } from "node:fs";const data: string[] = readFileSync(0, "utf8").trim().split(/\s+/);const n = Number(data[0]);const seats: string[] = data.slice(1, 1 + n);const start: string[] = [...seats]; // 복사본. const start = seats 는 같은 배열을 가리킨다const m = Number(data[1 + n]);let pos = 2 + n;for (let k = 0; k < m; k++, pos += 2) { const i = Number(data[pos]) - 1; const j = Number(data[pos + 1]) - 1; [seats[i], seats[j]] = [seats[j], seats[i]];}const now = new Map<string, number>(seats.map((name, k): [string, number] => [name, k]));const out: string[] = [seats.join(" ")];const moved: string[] = [];start.forEach((name, k) => { const at = now.get(name)!; if (at !== k) moved.push(`${name} ${k + 1} ${at + 1}`);});out.push(String(moved.length), ...moved);console.log(out.join("\n"));
JavaMain.java · 33 줄
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()); String[] seats = br.readLine().trim().split(" "); String[] start = seats.clone(); // String[] start = seats; 는 같은 배열을 가리킨다 int m = Integer.parseInt(br.readLine().trim()); for (int k = 0; k < m; k++) { StringTokenizer st = new StringTokenizer(br.readLine()); int i = Integer.parseInt(st.nextToken()) - 1; int j = Integer.parseInt(st.nextToken()) - 1; String tmp = seats[i]; seats[i] = seats[j]; seats[j] = tmp; } Map<String, Integer> now = new HashMap<>(); for (int k = 0; k < n; k++) now.put(seats[k], k); StringBuilder moved = new StringBuilder(); int count = 0; for (int k = 0; k < n; k++) { int at = now.get(start[k]); if (at != k) { count++; moved.append(start[k]).append(' ').append(k + 1).append(' ').append(at + 1).append('\n'); } } System.out.print(String.join(" ", seats) + "\n" + count + "\n" + moved); }}
C#Main.cs · 33 줄
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { int n = int.Parse(Console.ReadLine().Trim()); string[] seats = Console.ReadLine().Trim().Split(' '); string[] start = (string[])seats.Clone(); // string[] start = seats; 는 같은 배열을 가리킨다 int m = int.Parse(Console.ReadLine().Trim()); for (int k = 0; k < m; k++) { string[] p = Console.ReadLine().Trim().Split(' '); int i = int.Parse(p[0]) - 1, j = int.Parse(p[1]) - 1; (seats[i], seats[j]) = (seats[j], seats[i]); } var now = new Dictionary<string, int>(); for (int k = 0; k < n; k++) now[seats[k]] = k; var moved = new List<string>(); for (int k = 0; k < n; k++) { int at = now[start[k]]; if (at != k) moved.Add($"{start[k]} {k + 1} {at + 1}"); } var sb = new StringBuilder(); sb.Append(string.Join(" ", seats)).Append('\n').Append(moved.Count).Append('\n'); foreach (string line in moved) sb.Append(line).Append('\n'); Console.Write(sb); }}
C++main.cpp · 33 줄
#include <iostream>#include <string>#include <unordered_map>#include <utility>#include <vector>int main() { int n, m; std::cin >> n; std::vector<std::string> seats(n); for (auto& s : seats) std::cin >> s; std::vector<std::string> start = seats; // vector는 = 가 통째로 복사한다(참조가 아니다) std::cin >> m; for (int k = 0; k < m; k++) { int i, j; std::cin >> i >> j; std::swap(seats[i - 1], seats[j - 1]); } std::unordered_map<std::string, int> now; for (int k = 0; k < n; k++) now[seats[k]] = k; std::string out, moved; int count = 0; for (int k = 0; k < n; k++) out += (k ? " " : "") + seats[k]; for (int k = 0; k < n; k++) { int at = now[start[k]]; if (at != k) { count++; moved += start[k] + " " + std::to_string(k + 1) + " " + std::to_string(at + 1) + "\n"; } } std::cout << out << "\n" << count << "\n" << moved;}
Cmain.c · 37 줄
#include <stdio.h>#include <string.h>static char seats[1000][11];static char start[1000][11];int main(void) { int n, m; scanf("%d", &n); for (int k = 0; k < n; k++) scanf("%10s", seats[k]); memcpy(start, seats, sizeof seats); /* 배열은 = 로 복사할 수 없다: 칸을 통째로 복사 */ scanf("%d", &m); for (int k = 0; k < m; k++) { int i, j; char tmp[11]; scanf("%d %d", &i, &j); i--, j--; if (i == j) continue; /* 같은 칸끼리 strcpy 하면 겹친 복사라 안 된다 */ strcpy(tmp, seats[i]); strcpy(seats[i], seats[j]); strcpy(seats[j], tmp); } /* 처음 자리마다 지금 자리를 찾는다(n이 1000 이하라 차례로 찾아도 된다) */ static int at[1000]; int count = 0; for (int k = 0; k < n; k++) { for (int t = 0; t < n; t++) if (strcmp(seats[t], start[k]) == 0) { at[k] = t; break; } if (at[k] != k) count++; } for (int k = 0; k < n; k++) printf(k ? " %s" : "%s", seats[k]); printf("\n%d\n", count); for (int k = 0; k < n; k++) if (at[k] != k) printf("%s %d %d\n", start[k], k + 1, at[k] + 1); return 0;}
Craykonmain.cray · 35 줄
n = 콘솔.줄읽기().수로변환();seats = 콘솔.줄읽기().공백제거().나누기();// start = seats; 라면 같은 목록에 이름만 둘이다. 부분목록은 새 목록을 만든다start = seats.부분목록(0, seats.개수);m = 콘솔.줄읽기().수로변환();반복 (k = 0; k < m; k++){ p = 콘솔.수들읽기(); i = p[0] - 1; j = p[1] - 1; tmp = seats[i]; seats[i] = seats[j]; seats[j] = tmp;}now = 사전();반복 (k = 0; k < n; k++){ now[seats[k]] = k;}moved = [];반복 (k = 0; k < n; k++){ at = now[start[k]]; 만약 (at != k) { moved.넣기(start[k] + " " + (k + 1) + " " + (at + 1)); }}콘솔.쓰기(seats.잇기(" "));콘솔.쓰기(moved.개수);각각 (line 에서 moved){ 콘솔.쓰기(line);}