문제 82
단어 정렬
문장 $S$에는 알파벳 소문자로 이루어진 단어가 하나 이상 있으며, 인접한 두 단어는 공백 하나로 구분된다.
먼저 $S$의 모든 단어를 등장한 순서대로 출력한다. 그다음 모든 단어를 사전 순으로 정렬하여 다시 출력한다. 같은 단어가 여러 번 등장하면 등장한 횟수만큼 모두 출력한다.
사전 순서는 다음과 같이 정한다.
- 두 단어를 앞에서부터 한 글자씩 비교한다. 처음으로 서로 다른 글자가 나타나는 위치에서 알파벳 순으로 앞선 글자를 가진 단어가 먼저 온다.
- 한 단어가 다른 단어의 접두사라면 더 짧은 단어가 먼저 온다. 예를 들어,
app은apple보다 먼저 온다.
입력
첫 번째 줄에 문장 $S$가 주어진다. $S$에 포함된 단어의 수를 $K$라고 하자. $(1 \le \lvert S \rvert \le 200; 1 \le K \le 20)$
- $S$는 알파벳 소문자와 공백으로만 이루어져 있다.
- $S$의 처음과 끝은 공백이 아니며, 인접한 두 단어 사이에는 공백이 정확히 하나 있다.
출력
첫 번째 줄부터 $K$개의 줄에 걸쳐 $S$의 단어를 등장한 순서대로 한 줄에 하나씩 출력한다.
그다음 줄에 $S$의 모든 단어를 사전 순으로 정렬하여 공백으로 구분해 출력한다.
예제 입력 1
simple is best
예제 출력 1
simple is best best is simple
예제 입력 2
i am a boy
예제 출력 2
i am a boy a am boy i
예제 입력 3
to be or not to be
예제 출력 3
to be or not to be be be not or to to
노트
C 언어를 사용하는 경우, 이 문제의 사전 순은 C 언어의 strcmp 함수가 두 문자열을 비교하는 순서와 같다.
공식 해설
문장 전체를 한 줄 읽어 공백을 기준으로 단어 배열을 만든다. 먼저 이 배열을 앞에서부터 순회하여 단어를 한 줄에 하나씩 출력한다.
그다음 배열을 사전 순으로 정렬하고, 모든 단어를 공백으로 구분하여 한 줄에 출력한다. 문자열의 기본 사전 순 비교는 처음 다른 글자에서 순서를 정하고 한 단어가 다른 단어의 접두사이면 짧은 단어를 먼저 둔다. 따라서 문제의 비교 기준과 같다.
정렬은 순서만 바꾸므로 같은 단어도 등장 횟수만큼 그대로 남긴다. 원래 순서의 출력은 정렬 전에 해야 한다.
문장 길이를 $L$, 단어 수를 $K$, 가장 긴 단어 길이를 $D$라 하면 시간복잡도는 $O(L+DK\log(K+1))$, 공간복잡도는 $O(L+K)$이다.
구현 · 언어별 풀이
C++ 구현
getline으로 문장을 읽고 istringstream으로 단어를 나누어 vector<string>에 저장한다. 원래 순서의 출력을 마친 뒤 sort를 수행한다. 소문자 단어의 기본 문자열 비교가 문제의 사전 순과 같으므로 별도 비교 함수는 필요 없다.
C 구현
문장을 단어로 나누어 원래 순서대로 먼저 출력한다. 다음에는 단어 포인터 배열을 strcmp 비교로 qsort하여 출력할 수 있다. 같은 단어도 각각 남겨 정렬한 순서대로 출력한다.
Python 구현
S.split()으로 단어 리스트를 만들고 원래 순서대로 출력한 뒤 sort()한다. 정렬 후 다시 출력하며 중복 단어를 삭제하지 않는다. 소문자 단어의 기본 문자열 순서가 필요한 사전순이다.
Java 구현
문장의 단어를 split(" ")로 String[]에 저장한다. 원래 순서를 출력한 뒤 Arrays.sort(words)하고 다시 출력한다. 같은 단어도 배열에 그대로 남는다.
Rust 구현
split_whitespace()로 Vec<&str>을 만들고 원래 순서를 출력한다. 원문 String이 살아 있는 동안 sort_unstable()로 참조만 정렬해 다시 출력한다. 단어마다 String을 복사할 필요는 없다.
JavaScript 구현
문장에는 단어 사이에 공백 하나만 있으므로 s.split(' ')으로 단어 배열을 만든다. 먼저 입력 순서의 words.join('\n')을 출력하고, 그다음 words.sort()를 수행해 words.join(' ')을 출력한다.
숫자 정렬과 달리 이 문제의 소문자 단어는 기본 문자열 정렬이 필요한 사전순과 같다. localeCompare로 지역별 정렬 규칙을 적용할 필요가 없다. 같은 단어도 등장 횟수만큼 유지하고, 원래 순서의 출력 전에 정렬하지 않는다. 단어 수가 $20$ 이하라 출력 전체를 한 문자열로 모아도 충분히 작다.