문제 개요
하나의 패턴(pattern)과 하나의 문자열(str)이 주어졌을 때, 문자열이 해당 패턴을 따르는지 확인하는 문제입니다. 여기서 '패턴을 따른다'는 것은 패턴의 각 문자와 문자열 내의 비어 있지 않은 단어 사이에 전단사(bijection) 관계, 즉 일대일 대응이 성립한다는 의미입니다.
예를 들어 입력이 다음과 같다면:
- pattern = "cbbc"
- str = "word pattern pattern word"
출력은 True가 됩니다. 'c'는 'word'에, 'b'는 'pattern'에 각각 일관되게 대응되기 때문입니다.
해결 접근 방식
핵심 아이디어는 패턴과 단어열을 각각 동일한 규칙의 숫자 시퀀스로 변환한 뒤, 두 시퀀스가 일치하는지 비교하는 것입니다. 새로운 요소가 등장할 때마다 순차적으로 번호를 부여하면, 구조가 같다면 반드시 같은 숫자 시퀀스가 만들어집니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- 문자열 str을 스트림(strcin)으로 만들고, 공백 기준으로 단어를 하나씩 읽어
words벡터에 저장합니다. - 패턴용 맵
p2i(char → int)를 선언하고, 인덱스 i를 0으로 초기화한 뒤 빈 문자열 pat을 준비합니다. - pattern의 각 문자 c에 대해, c가 아직 p2i에 없다면 i를 1 증가시키고
p2i[c] = i로 저장합니다. - pat 뒤에
p2i[c]의 값을 문자열로 이어 붙여 패턴의 숫자 시퀀스를 완성합니다. - 같은 방식으로 단어용 맵
str2i(string → int)를 사용해 words의 각 단어를 숫자로 치환한 시퀀스 pat1을 만듭니다. - pat1과 pat이 서로 같으면 true, 아니면 false를 반환합니다.
이 방식은 전단사 조건도 자연스럽게 처리합니다. 서로 다른 문자나 단어에는 항상 새로운 번호가 부여되므로, 두 요소가 같은 번호를 가지려면 반드시 동일한 원래 값이어야 하기 때문입니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool wordPattern( string pattern, string str ) {
istringstream strcin(str);
string word;
vector<string> words;
while (strcin >> word)
words.push_back(word);
unordered_map<char, int> p2i;
int i = 0;
string pat = "";
for (auto c : pattern) {
if (p2i.count(c) == 0) {
i++;
p2i[c] = i;
}
pat += to_string(p2i[c]);
}
unordered_map<string, int> str2i;
i = 0;
string pat1 = "";
for (auto c : words) {
if (str2i.count(c) == 0) {
i++;
str2i[c] = i;
}
pat1 += to_string(str2i[c]);
}
return pat1 == pat;
}
};
main(){
Solution ob;
cout << (ob.wordPattern("cbbc", "word pattern pattern word"));
}코드 설명
istringstream을 사용하면 공백으로 구분된 단어를 손쉽게 추출할 수 있습니다.unordered_map은 평균 O(1)의 조회 성능을 제공하므로 전체 알고리즘의 시간 복잡도는 O(n + m)입니다(n은 패턴 길이, m은 단어 수).- 마지막에 두 숫자 시퀀스 문자열을 직접 비교하여 패턴 일치 여부를 판단합니다.
실행 결과
입력
"cbbc", "word pattern pattern word"
출력
1
출력값 1은 true를 의미하며, 주어진 문자열이 패턴 "cbbc"와 정확히 일대일 대응됨을 보여줍니다.