연극 대본에서 몇몇 말을 다른 말로 바꾸려 한다.
바꾸기 규칙은 "a b" 꼴이고, 대본 속의 a를 b로 바꾼다는 뜻이다.
규칙들은 하나씩 차례로 쓰지 않고, 모두 한꺼번에 쓴다.
그래서 "Tom Ann"과 "Ann Tom" 두 규칙이 있으면 두 이름이 서로 맞바뀐다.
대본의 줄마다 맨 앞 글자부터 왼쪽에서 오른쪽으로 살피며 다음과 같이 바꾼다.
지금 자리에서 시작하는 a를 가진 규칙 가운데 a가 가장 긴 규칙 하나를 고른다.
그런 규칙이 있으면 그 규칙의 b를 쓰고, a의 글자 수만큼 앞으로 간다.
그런 규칙이 없으면 지금 글자를 그대로 쓰고 한 글자 앞으로 간다.
써 넣은 b는 다시 살피지 않는다.
a가 낱말의 일부여도 바꾼다.
대문자와 소문자는 다른 글자이고, a와 b 속의 기호(. * ( \ $ 등)는 특별한 뜻 없이 그 글자 자체다.
첫 줄에 규칙 수 m, 다음 m줄에 규칙이 하나씩 주어진다.
그다음 줄에 대본의 줄 수 k, 다음 k줄에 대본이 한 줄씩 주어진다.
바꾼 대본을 입력 차례대로 k줄에 출력하라.
입력
1 ≤ m ≤ 50. a와 b는 빈칸 없는 ASCII 글자(코드 33~126) 1~10글자이고, a와 b 사이에는 빈칸이 하나 있다. 규칙들의 a는 모두 서로 다르다(a와 b는 같을 수도 있다). 1 ≤ k ≤ 20. 대본의 줄은 ASCII 글자(코드 32~126) 1~1,000글자이고 빈칸으로 시작하거나 끝나지 않는다
출력
k줄
예시 1 · stdin
3
Tom Ann
Ann Tom
To Mr.
2
Tom met Ann.
Ann told Tom: Today!
stdout
Ann met Tom.
Tom told Ann: Mr.day!
예시 2 · stdin
2
a.b x
x a.b
1
a.b axb x xx
stdout
x aa.bb a.b a.ba.b
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
핵심은 '한 번 훑으며 한꺼번에'예요. 언어마다 있는 바꾸기 함수(Python str.replace, JS·TS replaceAll, Java replace, C# Replace, 크레이콘 바꾸기)는 규칙 하나만 처리해서, 규칙마다 차례로 부르면 Tom→Ann 다음의 Ann→Tom이 방금 바꾼 것까지 되돌려 모두 Tom이 돼요. 그래서 자리마다 '여기서 시작하는 가장 긴 a'를 사전에서 찾아요. a는 10글자 이하이니 길이 10부터 1까지 잘라 사전에 있는지 물으면 돼요: Python dict, JS·TS Map.has, Java HashMap.containsKey, C# Dictionary.TryGetValue, C++ unordered_map::find, 크레이콘 사전()과 있나, 자르기는 부분문자열(i, len)이에요. C에는 사전이 없어 규칙 50개를 strncmp(text + i, a, len)으로 하나씩 견줘요. Python은 re.sub에 re.escape한 a들을 긴 것부터 |로 이어 주면 한 번에 돼요. 정규식의 |는 왼쪽 것부터 맞춰 보니 짧은 것이 앞에 있으면 To가 Tom을 가로채고, re.escape(JS는 직접 이스케이프)를 빼면 .이 아무 글자나 맞고 (는 정규식 오류가 나요. Java replaceAll도 정규식이라 같은 문제가 있고, 글자 그대로 바꾸는 것은 replace예요. 그 밖의 함정: 먼저 적힌 규칙을 고르기(가장 긴 것이어야 해요), 바꾼 뒤 한 글자만 넘어가 a의 나머지 글자를 다시 읽기, 바꾼 결과를 다시 훑어 b를 또 바꾸기.
Pythonmain.py · 14 줄
import reimport syslines = sys.stdin.read().split("\n")m = int(lines[0])rules = dict(line.split(" ") for line in lines[1:1 + m])k = int(lines[1 + m])# 긴 것부터 늘어놓은 a들을 | 로 잇는다. re.escape로 . * ( 같은 기호를 글자 그대로 찾게 한다.# 정규식의 | 는 왼쪽 것부터 맞춰 보므로, 긴 것이 앞에 있으면 그 자리에서 가장 긴 a가 걸린다.pattern = re.compile("|".join(re.escape(a) for a in sorted(rules, key=len, reverse=True)))for text in lines[2 + m:2 + m + k]: # re.sub는 왼쪽부터 한 번 훑고, 바꿔 넣은 글자는 다시 보지 않는다 print(pattern.sub(lambda mt: rules[mt.group()], text))
JavaScriptmain.js · 28 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const m = Number(lines[0]);const rules = new Map();for (const line of lines.slice(1, 1 + m)) { const [a, b] = line.split(" "); rules.set(a, b);}const k = Number(lines[1 + m]);function rewrite(text) { const out = []; let i = 0; while (i < text.length) { let len = Math.min(10, text.length - i); // 지금 자리에서 가장 긴 a부터 찾아본다 while (len > 0 && !rules.has(text.slice(i, i + len))) len--; if (len > 0) { out.push(rules.get(text.slice(i, i + len))); i += len; } else { out.push(text[i]); i++; } } return out.join("");}console.log(lines.slice(2 + m, 2 + m + k).map(rewrite).join("\n"));
TypeScriptmain.ts · 31 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const m = Number(lines[0]);const rules = new Map<string, string>();for (const line of lines.slice(1, 1 + m)) { const [a, b] = line.split(" "); rules.set(a, b);}const k = Number(lines[1 + m]);function rewrite(text: string): string { const out: string[] = []; let i = 0; while (i < text.length) { let len = Math.min(10, text.length - i); // 지금 자리에서 가장 긴 a부터 찾아본다 while (len > 0 && !rules.has(text.slice(i, i + len))) len--; const b = rules.get(text.slice(i, i + len)); if (len > 0 && b !== undefined) { out.push(b); i += len; } else { out.push(text[i]); i++; } } return out.join("");}console.log(lines.slice(2 + m, 2 + m + k).map(rewrite).join("\n"));
JavaMain.java · 37 줄
import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.HashMap;import java.util.Map;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int m = Integer.parseInt(in.readLine().trim()); Map<String, String> rules = new HashMap<>(); for (int r = 0; r < m; r++) { String[] p = in.readLine().split(" "); rules.put(p[0], p[1]); } int k = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int t = 0; t < k; t++) { String text = in.readLine(); int i = 0; while (i < text.length()) { int len = Math.min(10, text.length() - i); // 지금 자리에서 가장 긴 a부터 찾아본다 while (len > 0 && !rules.containsKey(text.substring(i, i + len))) len--; if (len > 0) { out.append(rules.get(text.substring(i, i + len))); i += len; } else { out.append(text.charAt(i)); i++; } } out.append('\n'); } System.out.print(out); }}
C#Main.cs · 43 줄
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { int m = int.Parse(Console.ReadLine().Trim()); var rules = new Dictionary<string, string>(); for (int r = 0; r < m; r++) { string[] p = Console.ReadLine().Split(' '); rules[p[0]] = p[1]; } int k = int.Parse(Console.ReadLine().Trim()); var out_ = new StringBuilder(); for (int t = 0; t < k; t++) { string text = Console.ReadLine(); int i = 0; while (i < text.Length) { int len = Math.Min(10, text.Length - i); string b = null; // 지금 자리에서 가장 긴 a부터 찾아본다 while (len > 0 && !rules.TryGetValue(text.Substring(i, len), out b)) len--; if (len > 0) { out_.Append(b); i += len; } else { out_.Append(text[i]); i++; } } out_.Append('\n'); } Console.Write(out_); }}
C++main.cpp · 42 줄
#include <algorithm>#include <iostream>#include <string>#include <unordered_map>int main() { std::ios::sync_with_stdio(false); int m, k; std::cin >> m; std::unordered_map<std::string, std::string> rules; for (int r = 0; r < m; r++) { std::string a, b; std::cin >> a >> b; rules[a] = b; } std::cin >> k; std::string text; std::getline(std::cin, text); // 수 뒤에 남은 줄 끝을 버린다 std::string out; for (int t = 0; t < k; t++) { std::getline(std::cin, text); size_t i = 0; while (i < text.size()) { size_t len = std::min<size_t>(10, text.size() - i); // 지금 자리에서 가장 긴 a부터 찾아본다 auto it = rules.end(); for (; len > 0; len--) { it = rules.find(text.substr(i, len)); if (it != rules.end()) break; } if (len > 0) { out += it->second; i += len; } else { out += text[i]; i++; } } out += '\n'; } std::cout << out;}
Cmain.c · 37 줄
#include <stdio.h>#include <string.h>static char from[50][11], to[50][11];static int flen[50];static char text[1002];int main(void) { int m, k; scanf("%d", &m); for (int r = 0; r < m; r++) { scanf("%10s %10s", from[r], to[r]); flen[r] = (int)strlen(from[r]); } scanf("%d ", &k); /* 수 뒤의 줄바꿈까지 건너뛴다(대본은 빈칸으로 시작하지 않는다) */ for (int t = 0; t < k; t++) { if (!fgets(text, sizeof text, stdin)) break; text[strcspn(text, "\r\n")] = '\0'; int n = (int)strlen(text); for (int i = 0; i < n;) { int best = -1; /* 이 자리에서 시작하는 a 가운데 가장 긴 것 */ for (int r = 0; r < m; r++) if (flen[r] <= n - i && (best < 0 || flen[r] > flen[best]) && strncmp(text + i, from[r], flen[r]) == 0) best = r; if (best >= 0) { fputs(to[best], stdout); i += flen[best]; } else { putchar(text[i]); i++; } } putchar('\n'); } return 0;}
Craykonmain.cray · 34 줄
m = 콘솔.줄읽기().수로변환();rules = 사전();반복 (r = 0; r < m; r++){ p = 콘솔.줄읽기().나누기(" "); rules[p[0]] = p[1];}k = 콘솔.줄읽기().수로변환();반복 (t = 0; t < k; t++){ text = 콘솔.줄읽기(); out = []; i = 0; 동안 (i < text.길이) { len = 수학.작은수(10, text.길이 - i); // 지금 자리에서 가장 긴 a부터 찾아본다 동안 (len > 0 && !rules.있나(text.부분문자열(i, len))) { len--; } 만약 (len > 0) { out.넣기(rules[text.부분문자열(i, len)]); i += len; } 아니면 { out.넣기(text[i]); i++; } } 콘솔.쓰기(out.잇기(""));}