[editorial] 2007년 서울 지역대회 인터넷 예선 A번 Letter Bank

  • admin
    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 님의 제보에 따라 첫번째 설명을 정정합니다. 이렇게도 틀리는 군요. --;

    • 구종만, algospot.com 운영진
      [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    17년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan

    정정했습니다! 확인부탁해요!


    17년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.