문제 소개
여러 개의 구절(phrase)로 이루어진 목록이 주어졌을 때, 이를 조합하여 만들 수 있는 전후 퍼즐(Before and After Puzzles) 목록을 생성하는 문제를 살펴보겠습니다. 여기서 구절이란 소문자 알파벳과 공백으로만 구성된 문자열을 의미하며, 시작과 끝에는 공백이 없고 연속된 공백도 존재하지 않는다고 가정합니다.
전후 퍼즐은 두 구절을 병합하여 만든 문장입니다. 이때 첫 번째 구절의 마지막 단어와 두 번째 구절의 첫 번째 단어가 서로 같아야 하며, 겹치는 단어는 하나만 남기고 이어 붙입니다. 모든 구절 쌍 phrases[i]와 phrases[j](i ≠ j)에 대해 만들 수 있는 퍼즐을 찾아야 하고, 두 구절을 연결하는 순서도 결과에 영향을 주므로 양방향을 모두 고려해야 합니다.
최종 답은 중복이 없는 고유한 문자열 목록이어야 하며, 사전순(lexicographic order)으로 정렬되어 있어야 합니다.
예시
입력이 다음과 같다고 가정해 보겠습니다.
phrases = ["mission statement", "a quick bite to eat", "a chip off the old block", "chocolate bar", "mission impossible", "a man on a mission", "block party", "eat my words", "bar of soap"]
이때 기대되는 출력은 다음과 같습니다.
["a chip off the old block party", "a man on a mission impossible", "a man on a mission statement", "a quick bite to eat my words", "chocolate bar of soap"]
예를 들어 "a chip off the old block"과 "block party"를 보면, 앞 구절의 마지막 단어 "block"이 뒤 구절의 첫 단어와 일치하므로 두 문장을 합쳐 "a chip off the old block party"라는 퍼즐이 완성됩니다.
풀이 접근 방법
이 문제는 해시 맵(unordered_map)을 활용하면 효율적으로 해결할 수 있습니다. 각 구절의 마지막 단어를 키로, 해당 구절의 인덱스를 값으로 미리 저장해 두면 다른 구절의 첫 단어와 빠르게 매칭할 수 있습니다. 단계별로 정리하면 다음과 같습니다.
- 문자열 벡터 ret을 준비하고, phrases 배열을 정렬합니다.
- 맵 m을 선언하고, n을 phrases 배열의 크기로 설정합니다.
- i를 0부터 n-1까지 반복합니다.
- s := phrases[i], rspace := 오른쪽에서부터 찾은 공백의 위치
- rspace가 없으면 s 전체를, 있으면 마지막 공백 이후 부분(마지막 단어)을 키로 하는 m의 리스트에 i를 삽입합니다.
- i를 0부터 n-1까지 다시 반복합니다.
- s := phrases[i], lspace := 왼쪽에서부터 찾은 공백의 위치
- x := lspace가 없으면 s 전체, 있으면 첫 공백 앞부분(첫 단어)
- m에 x가 키로 존재하면:
- v := m[x]
- j를 0부터 v의 크기까지 반복하면서, v[j]가 i가 아닌 경우 phrases[v[j]] + s.substr(x.size())를 ret에 추가합니다.
- ret을 정렬합니다.
- ret에서 중복을 제거한 뒤 반환합니다.
핵심 아이디어는 뒤에 오는 구절의 첫 단어 길이만큼 건너뛴 나머지 부분을 앞 구절 뒤에 그대로 붙이면, 겹치는 단어가 자연스럽게 하나로 합쳐진다는 점입니다.
C++ 구현 예제
다음 구현 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<string> beforeAndAfterPuzzles(vector<string>& phrases) {
vector <string> ret;
sort(phrases.begin(), phrases.end());
unordered_map <string, vector <int> > m;
int n = phrases.size();
for(int i = 0; i < n; i++){
string s = phrases[i];
auto rspace = s.rfind(' ');
m[rspace == string::npos ? s : s.substr(rspace + 1)].push_back(i);
}
for(int i = 0; i < n; i++){
string s = phrases[i];
auto lspace = s.find(' ');
string x = (lspace == string::npos? s : s.substr(0, lspace));
if(m.count(x)){
vector <int>& v = m[x];
for(int j = 0; j < v.size(); j++){
if(v[j] != i){
ret.push_back(phrases[v[j]] + s.substr(x.size()));
}
}
}
}
sort(ret.begin(), ret.end());
ret.erase(unique(ret.begin(), ret.end()), ret.end());
return ret;
}
};
main(){
vector<string> v = {"mission statement","a quick bite to eat","a chip off the old block","chocolate bar","mission impossible","a man on a mission","block party","eat my words","bar of soap"};
Solution ob;
print_vector(ob.beforeAndAfterPuzzles(v));
}
실행 결과
입력
["mission statement","a quick bite to eat","a chip off the old block","chocolate bar","mission impossible","a man on a mission","block party","eat my words","bar of soap"]
출력
[a chip off the old block party, a man on a mission impossible, a man on a mission statement, a quick bite to eat my words, chocolate bar of soap]
코드 설명 및 복잡도
위 코드의 핵심은 unordered_map에 각 구절의 마지막 단어를 키로, 해당 구절의 인덱스 목록을 값으로 저장하는 부분입니다. 이후 모든 구절에 대해 첫 번째 단어를 조회하여 매칭되는 구절이 있으면 두 문장을 병합하며, v[j] != i 조건으로 자기 자신과의 결합은 제외합니다.
결과 벡터를 정렬한 후 unique()와 erase()를 함께 사용하면 인접한 중복 원소가 제거되어, 사전순으로 정렬된 고유한 퍼즐 목록을 깔끔하게 얻을 수 있습니다.
구절의 개수를 N, 평균 문자열 길이를 L이라 하면, 해시 맵 덕분에 모든 쌍을 직접 비교하는 O(N²) 완전 탐색보다 유리하며, 전체 수행 시간은 대략 O(N × L + K log K)(K는 생성된 퍼즐 수) 수준으로 효율적입니다.