문제 84
단어 이어 붙이기 (대소문자)
두 문장 $S$, $T$와 두 정수 $M$, $N$이 주어진다. 각 문장의 단어 번호는 $0$부터 시작한다.
$S$의 $M$번째 단어와 $T$의 $N$번째 단어를 고른다. 두 단어 중 아래에서 정의한 순서가 앞서는 단어를 먼저, 다른 단어를 나중에 이어 붙인 문자열을 구하라.
두 단어의 순서는 다음과 같이 정한다.
- 두 단어를 앞에서부터 한 글자씩 비교한다. 처음으로 서로 다른 글자가 나타나는 위치에서 ASCII 코드 값이 작은 글자를 가진 단어가 먼저 온다.
- 한 단어가 다른 단어의 접두사라면 더 짧은 단어가 먼저 온다. 예를 들어,
app은apple보다 먼저 온다. - 두 단어가 같다면 어느 단어를 먼저 이어 붙여도 결과는 같다.
입력
문장 $S$, $T$에 포함된 단어의 수를 각각 $P$, $Q$라고 할 때, 첫 번째 줄에 두 정수 $M$, $N$이 공백으로 구분되어 주어진다. $(0 \le M < P; 0 \le N < Q)$
두 번째 줄에 문장 $S$가 주어진다. $(1 \le \lvert S \rvert \le 100; 1 \le P \le 20)$
세 번째 줄에 문장 $T$가 주어진다. $(1 \le \lvert T \rvert \le 100; 1 \le Q \le 20)$
- $S$와 $T$는 알파벳 대문자와 소문자, 공백으로 이루어져 있다.
- 각 문장의 처음과 끝은 공백이 아니며, 인접한 두 단어 사이에는 공백이 정확히 하나 있다.
출력
첫 번째 줄에 $S$의 $M$번째 단어와 $T$의 $N$번째 단어를 문제에서 정의한 순서대로 이어 붙인 문자열을 출력한다.
예제 입력 1
2 4 book desk pencil paper orange apple banana lemon grape
예제 출력 1
grapepencil
예제 입력 2
0 1 Zebra runs fast I like apples
예제 출력 2
Zebralike
예제 입력 3
1 0 my Apple pie apple Tree
예제 출력 3
Appleapple
노트
C 언어를 사용하는 경우, 이 문제에서 정의한 순서는 C 언어의 strcmp 함수가 두 문자열을 비교하는 순서와 같다.
공식 해설
두 문장을 공백을 기준으로 단어들로 나누고, $S$에서 인덱스 $M$인 단어와 $T$에서 인덱스 $N$인 단어를 고른다. 단어 번호는 $0$부터 시작한다.
고른 두 단어를 앞에서부터 비교한다. 처음 다른 문자의 ASCII 값이 작은 단어가 앞서고, 한 단어가 다른 단어의 접두사이면 짧은 단어가 앞선다. 이는 문제에서 정한 비교 기준이므로 대소문자를 바꾸거나 무시하지 않는다.
앞서는 단어를 먼저, 나머지 단어를 그 뒤에 공백 없이 이어 출력한다. 같은 단어라면 어느 쪽을 먼저 두어도 결과가 같다.
시간복잡도와 공간복잡도는 $O(\lvert S\rvert+\lvert T\rvert)$이다.
구현 · 언어별 풀이
C++ 구현
정수 두 개를 읽은 뒤 getline(cin >> ws, S)로 첫 문장을 읽고, 다음 문장도 한 줄로 읽는다. 각 문장은 istringstream으로 나누어 원하는 단어를 선택한다. 선택한 두 string을 비교하여 작은 쪽부터 이어 출력한다.
C 구현
정수 입력 뒤 남은 개행을 처리하고 fgets로 두 문장을 읽는다. 각 문장에서 공백을 세어 0-based M,N번째 단어를 찾고 strcmp로 비교한다. 공백을 제거하거나 대소문자를 통일하지 않는다.
Python 구현
두 문장을 각각 readline()으로 읽어 split()한다. 첫 줄 M,N은 0-based 인덱스이므로 그대로 사용한다. 소문자화하지 않고 문자열 비교를 해야 ASCII 대문자 순서가 유지된다.
Java 구현
BufferedReader로 세 줄을 구분해 읽는다. 각 문장을 split(" ")하여 0-based M,N 단어를 선택하고 compareTo로 비교한다. equalsIgnoreCase나 소문자 변환은 필요 없다.
Rust 구현
입력을 줄 단위로 나누고 각 문장에서 split_whitespace().nth(M 또는 N)으로 선택한다. 전체 입력을 한 토큰열로 합쳐 두 문장의 경계를 잃지 않는다. 원래 대소문자로 str을 비교한다.
JavaScript 구현
첫 줄의 두 번호와 다음 두 문장을 줄 단위로 읽는다. 각각 split(' ')한 배열에서 $M$, $N$번째 단어를 그대로 고른다. 번호가 이미 $0$부터 시작하므로 $1$을 빼지 않는다.
알파벳 대문자·소문자의 ASCII 순서는 JS 문자열의 <= 비교와 같다. toLowerCase()나 지역별 localeCompare()를 적용하지 않는다. 앞서는 단어와 나머지 단어를 a <= b ? a + b : b + a로 공백 없이 이어 출력한다. 입력 문장을 전부 한 토큰 목록으로 바꾸면 두 문장의 경계를 잃기 쉬우므로 줄 구조를 유지한다.