문제 83
거꾸로 된 사전
두 단어 $A$, $B$가 주어진다. 사전 순으로 뒤에 오는 단어를 먼저, 앞에 오는 단어를 나중에 이어 붙인 문자열을 구하라. 두 단어가 같다면 어느 단어를 먼저 이어 붙여도 결과는 같다.
사전 순서는 다음과 같이 정한다.
- 두 단어를 앞에서부터 한 글자씩 비교한다. 처음으로 서로 다른 글자가 나타나는 위치에서 알파벳 순으로 앞선 글자를 가진 단어가 먼저 온다.
- 한 단어가 다른 단어의 접두사라면 더 짧은 단어가 먼저 온다. 예를 들어,
sejong은sejongdae보다 먼저 온다.
입력
첫 번째 줄에 알파벳 소문자로 이루어진 단어 $A$가 주어진다. $(1 \le \lvert A \rvert \le 50)$
두 번째 줄에 알파벳 소문자로 이루어진 단어 $B$가 주어진다. $(1 \le \lvert B \rvert \le 50)$
출력
첫 번째 줄에 문제에서 설명한 순서대로 $A$와 $B$를 이어 붙인 문자열을 출력한다.
예제 입력 1
sejong university
예제 출력 1
universitysejong
예제 입력 2
zebra apple
예제 출력 2
zebraapple
공식 해설
두 단어를 사전 순으로 비교하여 뒤에 오는 단어를 먼저 출력하고 다른 단어를 바로 이어 출력한다. $A\ge B$이면 $A+B$, 아니라면 $B+A$이다.
앞에서부터 처음 다른 글자로 순서를 정하고, 한 단어가 다른 단어의 접두사이면 더 긴 단어가 뒤에 온다. 두 단어가 같으면 어느 쪽을 먼저 출력해도 결과가 같다.
비교 대상은 두 단어 자체이다. $A+B$와 $B+A$를 비교하여 더 큰 문자열을 고르는 문제는 아니다.
시간복잡도와 문자열을 저장하는 공간복잡도는 $O(\lvert A\rvert+\lvert B\rvert)$이다.
구현 · 언어별 풀이
C++ 구현
string의 사전 순 비교로 A < B이면 $B$부터, 아니라면 $A$부터 출력한다. cout에 두 문자열을 차례로 전달하면 중간에 새 문자열을 만들지 않고도 이어 출력할 수 있다.
C 구현
strcmp(A,B)의 부호로 두 단어 자체의 사전순을 비교한다. 더 큰 단어부터 이어 출력한다. A+B와 B+A를 비교하는 최대 이어붙이기 알고리즘은 이 문제의 조건과 다르다.
Python 구현
A>B로 단어 자체를 비교하고 큰 단어를 먼저 출력한다. 한 단어가 다른 단어의 접두사이면 더 긴 단어가 크다. 이어 붙인 결과끼리 비교하지 않는다.
Java 구현
String.compareTo()로 A와 B 자체를 비교한다. 결과의 부호만 사용하고 더 큰 단어를 앞에 둔다. 접두사 관계도 기본 비교가 처리한다.
Rust 구현
str의 Ord 비교로 A,B 자체의 순서를 정한다. 소문자 ASCII에서 이 비교가 사전순과 같다. 큰 단어부터 출력하며 새로 이어 붙인 두 후보를 비교하지 않는다.
JavaScript 구현
두 줄의 소문자 단어를 읽고 a >= b로 단어 자체를 비교한다. 더 큰 단어를 앞에 이어 붙인다.
console.log(a >= b ? a + b : b + a);JS의 기본 문자열 비교는 이 입력에서 필요한 ASCII 사전순과 같다. 한 단어가 다른 단어의 접두사이면 긴 단어가 뒤에 온다. 이어 붙인 결과가 아니라 단어 자체의 사전순으로 앞에 놓을 단어를 정한다.