영어 소문자로 된 낱말 s가 한 줄에 주어진다.
s의 글자를 모두 한 번씩 써서 만들 수 있는 서로 다른 낱말을 사전 순(앞 글자부터 비교해 알파벳이 앞선 쪽이 먼저)으로 한 줄에 하나씩 모두 출력하라.
s에 같은 글자가 여러 번 있으면 같은 낱말이 여러 번 생길 수 있는데, 한 번만 출력한다(aab이면 aab, aba, baa).
aab
aab aba baa
cab
abc acb bac bca cab cba
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
재귀 하나로 겹침과 차례를 함께 해결해요.
글자마다 남은 개수를 세어 두고, 자리마다 "남은 글자 가운데 하나"를 a부터 차례로 골라 다음 자리로 내려가요(고른 뒤에는 개수를 되돌려요).
같은 글자는 한 자리에서 한 번만 고르니 같은 낱말이 다시 생기지 않고, 작은 글자부터 고르니 저절로 사전 순이 돼요.
흔한 함정은 둘이에요.
Python itertools.permutations는 글자가 아니라 자리를 서로 다르게 봐서 aab에서 aab가 두 번 나와요.
자리 바꾸기(swap)로 만드는 방법은 겹침을 지워도 사전 순으로 나오지 않아요.
언어마다 도구도 달라요.
C++ std::next_permutation은 정렬된 글자에서 시작하면 겹침 없이 사전 순으로 다음 순열을 줘요(재귀 없이).
다른 언어에는 이런 표준 함수가 없어요.
7글자면 최대 5,040줄이라, Java·C#은 StringBuilder에 모아 한 번에 써요.
크레이콘은 함수 늘어놓기(prefix)가 자기 자신을 부르고, 끝까지 가면 돌려주기;로 돌아와요.
줄은 문자열 out에 모았다가 콘솔.이어쓰기(out)로 한 번에 써요.
import sys s = input().strip()letters = sorted(set(s)) # 쓸 수 있는 글자(작은 것부터)left = {c: s.count(c) for c in letters} # 글자마다 남은 개수out = [] def arrange(prefix): if len(prefix) == len(s): out.append(prefix) return # 같은 글자는 이 자리에서 한 번만 고르니 겹친 줄이 생기지 않고, 작은 글자부터 고르니 사전 순이 된다 for c in letters: if left[c] > 0: left[c] -= 1 arrange(prefix + c) left[c] += 1 arrange("")sys.stdout.write("\n".join(out) + "\n")const s = require("fs").readFileSync(0, "utf8").trim();const letters = [...new Set(s)].sort(); // 쓸 수 있는 글자(작은 것부터)const left = new Map(letters.map((c) => [c, [...s].filter((x) => x === c).length]));const out = []; function arrange(prefix) { if (prefix.length === s.length) { out.push(prefix); return; } // 같은 글자는 이 자리에서 한 번만 고르니 겹친 줄이 생기지 않고, 작은 글자부터 고르니 사전 순이 된다 for (const c of letters) { if (left.get(c) > 0) { left.set(c, left.get(c) - 1); arrange(prefix + c); left.set(c, left.get(c) + 1); } }} arrange("");console.log(out.join("\n"));import { readFileSync } from "node:fs";const s: string = readFileSync(0, "utf8").trim();const letters: string[] = [...new Set(s)].sort(); // 쓸 수 있는 글자(작은 것부터)const left = new Map<string, number>(letters.map((c) => [c, [...s].filter((x) => x === c).length]));const out: string[] = []; function arrange(prefix: string): void { if (prefix.length === s.length) { out.push(prefix); return; } // 같은 글자는 이 자리에서 한 번만 고르니 겹친 줄이 생기지 않고, 작은 글자부터 고르니 사전 순이 된다 for (const c of letters) { const k = left.get(c)!; if (k > 0) { left.set(c, k - 1); arrange(prefix + c); left.set(c, k); } }} arrange("");console.log(out.join("\n"));import java.util.Scanner; public class Main { static int[] left = new int[26]; // 글자마다 남은 개수 static char[] path; static StringBuilder out = new StringBuilder(); static void arrange(int depth) { if (depth == path.length) { out.append(path).append('\n'); return; } // 같은 글자는 이 자리에서 한 번만 고르니 겹친 줄이 생기지 않고, a부터 고르니 사전 순이 된다 for (int c = 0; c < 26; c++) { if (left[c] > 0) { left[c]--; path[depth] = (char) ('a' + c); arrange(depth + 1); left[c]++; } } } public static void main(String[] args) { String s = new Scanner(System.in).next(); for (char ch : s.toCharArray()) left[ch - 'a']++; path = new char[s.length()]; arrange(0); System.out.print(out); }}using System;using System.Text; class Program{ static int[] left = new int[26]; // 글자마다 남은 개수 static char[] path; static StringBuilder output = new StringBuilder(); static void Arrange(int depth) { if (depth == path.Length) { output.Append(path).Append('\n'); return; } // 같은 글자는 이 자리에서 한 번만 고르니 겹친 줄이 생기지 않고, a부터 고르니 사전 순이 된다 for (int c = 0; c < 26; c++) { if (left[c] > 0) { left[c]--; path[depth] = (char)('a' + c); Arrange(depth + 1); left[c]++; } } } static void Main() { string s = Console.ReadLine().Trim(); foreach (char ch in s) left[ch - 'a']++; path = new char[s.Length]; Arrange(0); Console.Write(output); }}#include <array>#include <iostream>#include <string> std::array<int, 26> left{}; // 글자마다 남은 개수std::string path, out; void arrange(std::size_t depth) { if (depth == path.size()) { out += path; out += '\n'; return; } // 같은 글자는 이 자리에서 한 번만 고르니 겹친 줄이 생기지 않고, a부터 고르니 사전 순이 된다 for (int c = 0; c < 26; c++) { if (left[c] > 0) { left[c]--; path[depth] = static_cast<char>('a' + c); arrange(depth + 1); left[c]++; } }} int main() { std::string s; std::cin >> s; for (char ch : s) left[ch - 'a']++; path.assign(s.size(), ' '); arrange(0); std::cout << out;}#include <stdio.h>#include <string.h> static int left[26]; // 글자마다 남은 개수static char path[8];static int n; static void arrange(int depth) { if (depth == n) { puts(path); return; } // 같은 글자는 이 자리에서 한 번만 고르니 겹친 줄이 생기지 않고, a부터 고르니 사전 순이 된다 for (int c = 0; c < 26; c++) { if (left[c] > 0) { left[c]--; path[depth] = 'a' + c; arrange(depth + 1); left[c]++; } }} int main(void) { char s[8]; scanf("%7s", s); n = strlen(s); for (int i = 0; i < n; i++) left[s[i] - 'a']++; path[n] = '\0'; arrange(0); return 0;}// 같은 글자는 이 자리에서 한 번만 고르니 겹친 줄이 생기지 않고, 작은 글자부터 고르니 사전 순이 된다늘어놓기(prefix){ 만약 (prefix.길이 == s.길이) { out += prefix + "\n"; 돌려주기; } 반복 (i = 0; i < letters.개수; i++) { 만약 (left[i] > 0) { left[i] -= 1; 늘어놓기(prefix + letters[i]); left[i] += 1; } }} s = 콘솔.줄읽기().공백제거();// 쓸 수 있는 글자(작은 것부터)와 글자마다 남은 개수letters = [];각각 (c 에서 s){ 만약 (!letters.있나(c)) { letters.넣기(c); }}letters.정렬();left = 새목록(letters.개수, 0);각각 (c 에서 s){ left[letters.자리찾기(c)] += 1;}out = "";늘어놓기("");콘솔.이어쓰기(out);