Lv1_[옹알이(2), C++] 알고리즘 정리 - 프로그래머스 (map, 재귀함수 사용)

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

입력으로 문자열 배열(babbling)과 조카의 발음을 비교하기 쉽게 구분을 했습니다.

조카의 발음을 알파벳으로 구분해서 map에 저장해두는 방식을 사용
이유는 네 가지 발음만 사용할 수 있기 때문에 다른 발음이 들어오면 발음을 할 수 없기 때문이죠.
ex) "yezma"가 입력일 때, z가 들어오면 발음할 수 없는 알파벳이므로 해당 문자열은 발음하지 못하는 것으로 결론내릴 수 있음.

- map<char, map<string, unsigned int>> _m;
- map<'알파벳', map<'첫 알파벳으로 시작하는 발음', '발음의 길이'> >
(※map 대신 unordered_map을 사용해도됨. 조건과 상황에 따라 변경 가능)

와 같은 형태로 저장된다.

이렇게 구성을 하는 이유는 검색 속도를 높이기 위함이다.
지금 예시에는 발음이 4개 뿐이 없어서 단순 반복문(for)으로 검색해도 검색 속도에 큰 문제는 없다고 생각하지만 발음의 수가 점점 많아질 수록 효율이 떨어지게 된다.
그래서 1차는 알파벳으로 분류, 2차는 단어별로 저장해두었다.


그렇다면 구분해둔 조카의 발음과 입력된 문자열과 비교는 어떻게 할 것인가.

문제 해결하기 위한 알고리즘

1) 문자열의 처음 알파벳부터 시작
2) 알파벳과 일치하는 발음 찾음
3) 찾은 발음과 동일한 길이의 문자열이 일치 여부를 확인
3-1) 일치하면 일치한 문자열 다음 index로 이동
3-2) 일치하지 않거나 이전에 찾은 발음과 동일하면 '발음 불가능한 문자열'로 구분 후 종료
4) 다시 2) 부터 반복. index 변화와 이전에 찾은 발음만 변경되었음
5) 발음과 문자열이 모두 일치하면 '발음 가능한 문자열'로 구분 후 종료

각 단계은 재귀함수[search_SameWord()]로 동작하고 매개변수 인덱스(index), 이전 발음(before_str)만 변경된다.
(※ 재귀함수를 사용한 이유는 문제에서 제시한 예시와 조건보다 더 많은 조건과 예외상황을 대처하기 위함이다. 자세한 내용은 예시 설명 이후 추가 작성)

종료 시점은 모두 일치(index==문자열크기) 했을 때와 발음이 일치하지 않거나 동일 발음이 연속 반복 되었을 때다.

밑에서 그림의 예시로 보면
- 발 음 : { "aya", "ye", "woo", "ma" }
- 문자열 : "ayaye"

위 예제는 모든 발음이 일치하므로 '발음 가능한 문자열'로 구분된다.


- 발 음 : { "aya", "ye", "woo", "ma" }
- 문자열 : "ayazye"

index 3에 'z'는 조카의 발음에 포함되어 있지 않은 알파벳이다.
그렇기 때문에 '발음 불가능한 문자열'로 구분함.


- 발 음 : { "aya", "ye", "woo", "ma" }
- 문자열 : "yeye"

ye, ye가 반복되기 때문에 '발음 불가능한 문자열'로 구분함.

---

※ 문제 조건 보다 확장해서 예외 처리까지 한 내용

여기서 더 나아가 조카가 유사한 발음까지 할 수 있다는 조건을 추가한다면 어떨까?

같은 알파벳으로 시작하는 단어를 늘리고 유사 단어까지 (at, atm), ('ye', 'yem') 추가해줬다.
- 발음 : { "aya", "at", "atm", "ye", "yem", "woo", "ma" }

표와 같이 map에 저장이 된다.

1) 첫번째 예시
- 발 음 : { "aya", "at", "atm", "ye", "yem", "woo", "ma" }
- 문자열 : "atmawoo"

성공하는 발음은 'at' 'ma' 'woo'가 된다.
첫 시작이 'aya'이면 발음이 일치하지 않기 때문에 false(발음 불가능 문자열)로 판단되고 'at', 'atm'가 되는 경우는 성공한다.
성공한 2개 발음('at', 'atm')은 자신이 가진 경우수를 모두 따져서 발음 여부를 따져야한다.
· 'at' → 'ma' → 'woo' (성공)
· 'atm' → 'aya' (실패)
· 'atm' → 'at' (실패)
· 'atm' → 'atm' (실패)


2) 두 번째 예시 [유사 발음들이 섞여있을 때 동작 방식]
- 발 음 : { "aya", "at", "atm", "ye", "yem", "woo", "ma" }
- 문자열 : "yemayemat"

· 'ye' → 'ma' → 'ye' → 'ma' → 't' (실패)
· 'ye' → 'ma' → 'yem' → 'at' (성공)
· 'yem' → 'at' (실패)
· 'yem' → 'atm' (실패)
· 'yem' → 'aya' (실패)

유사한 단어가 들어왔을 때까지도 대처할 수 있도록 코드를 구성했다.
옹알이(2)를 풀 때 이정도까지 신경 쓸 필요는 없지만 이왕에 짜는거 생각나는 예외상황까지 추가를 해봤다.

소스코드

bool search_SameWord(std::map<char, std::map<std::string, unsigned int>> _m, const std::string str, unsigned int indexCount, std::string before_str, int DebugLv = 1) {
    bool isSameValue = false;
    const unsigned int str_length = str.length();
    if(str_length == indexCount) {
        std::cout << "str_length == indexCount" << std::endl;
        isSameValue = true;
        return isSameValue;
    }
 
    char c_num = str[indexCount];
    std::cout << "indexCount : " << indexCount << ", c_num : " << c_num << std::endl;
    std::map<std::string, unsigned int>::iterator iter;
    std::map<std::string, unsigned int> tmp_m = _m[c_num];
    
    for(iter = tmp_m.begin(); iter != tmp_m.end(); iter++) {
        const std::string key = iter->first;
        const unsigned int size = iter->second;
        std::cout << "DebugLv : " << DebugLv << std::endl;
        std::cout << "key : " << key << ", size : " << size << std::endl;
 
        if(str_length >= (indexCount + size)) {
            const std::string tmp_str(str.begin() + indexCount, str.begin() + indexCount + size);
            std::cout << "tmp_str : " << tmp_str << std::endl;
 
            if(key.compare(tmp_str) == 0) {
                if(key.compare(before_str) != 0) {
                    std::cout << "Same str" << std::endl << std::endl;
                    before_str = tmp_str;
                    isSameValue = search_SameWord(_m, str, (indexCount + size), before_str, (DebugLv + 1));
                    
                    if(isSameValue == true) {
                        break;
                    }
                } else {
                    std::cout << "Fail! Same before_str key : [" << before_str << "]" << std::endl;
                }
            } else {
                std::cout << "Fail! diifer key : [" << key << "], tmp_str : [" << tmp_str << "]" << std::endl;
            }
            std::cout << std::endl;
        } else {
            std::cout << "Fail! Size Over!" << std::endl;
        }
    }
 
    return isSameValue;
 
}
 
 
 
int solution(std::vector<std::string> babbling) {
    int answer = 0;
    std::vector<std::string> able_word = { "aya", "ye", "woo", "ma" };
    std::map<char, std::map<std::string, unsigned int>> _m;
 
    for(char i = 'a'; i <= 'z'; i++) {
        std::map<std::string, unsigned int> tmp_m;
        _m.insert(make_pair(i, tmp_m));
    }
 
    for(auto item : able_word) {
        if(item.length() > 0) {
            char first_alp = item[0];
            _m[first_alp].insert(make_pair(item, item.length()));
        }
    }
 
    for(auto str : babbling) {
        bool isSuccess = false;
        std::cout << "target str : " << str << std::endl;
        
        // const unsigned int str_length = str.length();
        unsigned int indexCount = 0;
        std::string before_str = "";
 
        isSuccess = search_SameWord(_m, str, indexCount, before_str);
 
        if(isSuccess == true) {
            std::cout << "@@isSuccess str : " << str << std::endl;
            answer++;
        } else {
            std::cout << "##failed str : " << str << std::endl;
        }
        std::cout << std::endl;
    }
 
 
    std::cout << "answer : " << answer << std::endl;
    return answer;
}

(※ 코드 내에 로그기록(cout, endl)이 포함되어 있으면 통과 속도가 느려지므로 프로그래머스 돌릴 때는 제거하고 돌리는 것이 좋음. 아래의 테스트 시간은 로그를 전부 제거하고 돌렸을 때의 결과임)

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓