[문제 보러 가기]
이 문제는 제출 성공률(46%) 이나 제출 성공 횟수(252회) 를 보면 알 수 있듯이 예선 문제 중 가장 쉬운 문제입니다. 문제를 이해하는 것도 어렵지 않고, 입력의 크기도 작은 편입니다. 하지만 46% 라는 성공률은 여전히 두 번의 제출 중 한 번의 제출은 실패했다는 뜻이지요. 따라서 이런 문제에서는 틀릴 가능성을 최소화할 수 있는 가능한한 쉽고 간결한 방법으로 코딩하는 것이 중요합니다. 이럴 때는 자신이 사용하는 언어 표준 라이브러리의 문자열 등의 기능들을 잘 알아 두는 것이 유리합니다.
가장 단순한 방법은, 두 단어가 포함하는 알파벳의 집합이 같다면 답이 YES 이고, 아니면 답이 NO 라는 것에 착안해 첫 번째 단어에 들어 있는 모든 글자에 대해서 두 번째 단어에 들어있는지를 검사하는 함수를 작성하는 것입니다. 다음은 이의 간단한 C++ 구현입니다.
[spoiler="더 보기..."]
bool isWordBank(const string& bank, const string& str) {
for(size_t i = 0; i < bank.size(); ++i)
if(str.find(bank[i]) == string::npos)
return false;
return true;
}
[/spoiler]
이 때 isWordBank(a, b) == isWordBank(b, a) == true 이면 YES 가 답이 되고, 아니면 NO 가 됨을 알 수 있습니다.
아니면 다른 방법도 있습니다. 두 단어를 모두 sort 하고 중복을 제거해서 같은 문자열이 되는지를 보는 것입니다. 이와 같이 두 문자열을 공통적인 표준형(canonical form) 으로 변환하는 방법은 자주 쓰이면서도 굉장히 유용합니다. 다음 소스 코드는 C++ STL 의 알고리즘을 이용해 이 문제를 간단히 구현합니다.
[spoiler="더 보기..."]
int main() {
string a, b;
int cases;
cin >> cases;
while(cases--) {
cin >> a >> b;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
b.erase( unique(b.begin(), b.end()), b.end());
cout << (a == b ? "YES" : "NO") << endl;
}
}
[/spoiler]
정정: Being 님의 제보에 따라 첫번째 설명을 정정합니다. 이렇게도 틀리는 군요. --;
admin
[문제 보러 가기]
이 문제는 제출 성공률(46%) 이나 제출 성공 횟수(252회) 를 보면 알 수 있듯이 예선 문제 중 가장 쉬운 문제입니다. 문제를 이해하는 것도 어렵지 않고, 입력의 크기도 작은 편입니다. 하지만 46% 라는 성공률은 여전히 두 번의 제출 중 한 번의 제출은 실패했다는 뜻이지요. 따라서 이런 문제에서는 틀릴 가능성을 최소화할 수 있는 가능한한 쉽고 간결한 방법으로 코딩하는 것이 중요합니다. 이럴 때는 자신이 사용하는 언어 표준 라이브러리의 문자열 등의 기능들을 잘 알아 두는 것이 유리합니다.
가장 단순한 방법은, 두 단어가 포함하는 알파벳의 집합이 같다면 답이 YES 이고, 아니면 답이 NO 라는 것에 착안해 첫 번째 단어에 들어 있는 모든 글자에 대해서 두 번째 단어에 들어있는지를 검사하는 함수를 작성하는 것입니다. 다음은 이의 간단한 C++ 구현입니다.
[spoiler="더 보기..."]
bool isWordBank(const string& bank, const string& str) {
for(size_t i = 0; i < bank.size(); ++i)
if(str.find(bank[i]) == string::npos)
return false;
return true;
}
[/spoiler]
이 때 isWordBank(a, b) == isWordBank(b, a) == true 이면 YES 가 답이 되고, 아니면 NO 가 됨을 알 수 있습니다.
아니면 다른 방법도 있습니다. 두 단어를 모두 sort 하고 중복을 제거해서 같은 문자열이 되는지를 보는 것입니다. 이와 같이 두 문자열을 공통적인 표준형(canonical form) 으로 변환하는 방법은 자주 쓰이면서도 굉장히 유용합니다. 다음 소스 코드는 C++ STL 의 알고리즘을 이용해 이 문제를 간단히 구현합니다.
[spoiler="더 보기..."]
int main() {
string a, b;
int cases;
cin >> cases;
while(cases--) {
cin >> a >> b;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
b.erase( unique(b.begin(), b.end()), b.end());
cout << (a == b ? "YES" : "NO") << endl;
}
}
[/spoiler]
정정: Being 님의 제보에 따라 첫번째 설명을 정정합니다. 이렇게도 틀리는 군요. --;
16년 전