[백준 2607] - 비슷한 단어(구현, 문자열) C++

문제

https://www.acmicpc.net/problem/2607

2607번: 비슷한 단어

접근방법

사이즈가 같은 경우와 한 사이즈 작은 경우, 한 사이즈 큰 경우를 나눠서 계산했다.

 

map을 복사해와서, word에 있는 알파벳이 cand에 몇개 존재하냐를 세는 것이 포인트다.

 

만약 word에 D가 2개 있을 경우,

cand에 D가 3개 있다면, 3개를 다 세면 안되고 2개만 세야하기 때문에 세면서 하나씩 빼준다.

cand에 D가 1개 있다면, 1개만 셀 것이기 때문에 match가 word.size()와는 분명 달라질 것이다.

이 때는 cand.size()가 무조건 word.size()보다 같거나 한 사이즈 작아야한다.

만약 cand에 word에 없는 다른 단어가 하나 더 존재한다면, mismatching이다.

 

 

코드

int n;
string word;

int compare(map<char, int> alpha_cnt, string cand) {
    int match = 0;
    for (auto c : cand) 
        if (alpha_cnt[c] > 0) {
            alpha_cnt[c]--;
            match++;
        }
    //사이즈가 같은 경우
    if (cand.size() == word.size() && (match == word.size() || match == word.size()-1)) return 1;
    //cand의 사이즈가 word보다 큰 경우, 
    if (cand.size() == word.size() + 1 && (match == word.size())) return 1;
    //cand의 사이즈가 word보다 작은 경우.
    if (cand.size() == word.size() - 1 && (match == word.size()-1)) return 1;
    return 0;
}

int main() {

    int answer = 0;
    cin >> n;
    cin >> word;
    map<char, int> alpha_cnt;
    for(auto w : word) alpha_cnt[w]++;
    FOR(i, n-1) {
        string cand;
        cin >> cand;
        answer += compare(alpha_cnt, cand);
    }
    cout << answer << endl;
    return 0;
}

개선할 점

2

D

DDD

 

위 같은 케이스에서는 cand가 word보다 사이즈가 2만큼 크지만, match는 1로 일치한다.

 

이런 케이스가 있을 거라고 생각하지 못해서, 많이 헤멨다.

 

확실하지 않은 경우 조금 더 타이트하게 조건문을 설정해주는 것이 좋을 것 같다.

위와 같은 경우에서는 처음 cand.size() > word.size()와 같이 설정했는데,

어차피 cand.size() - 1== word.size()만 정답이 될 수 있으므로,

이렇게 설정하는 것이 생각하지 못한 예외 케이스를 방지하는 데에 도움이 될 것 같다.

 

구현 위주 문제를 많이 풀어봐야겠다.