[L2] 프로그래머스 모음사전 C++ 해시맵, 백트래킹

리뷰

프로그래머스

 

백트래킹을 통해 각 모음 조합이 몇번째 단어인지 구해 해시맵에 기록해 놓고 입력받은 문자열을 key로 하는 해시맵의 value를 리턴하는 문제

 

 

전역 변수

• dic : 모음 조합으로 만든 단어를 key로 하고, 해당 단어가 몇번째 단어인지를 value로 받는 해시맵
• s : 백트래킹에서 모음의 종류 AEIOU를 순회하기 위한 문자열
• idx : n번째를 기록하기 위한 변수, 초깃값은 0이다.

 

함수

1. bt

void bt(int level, string str)

 

각 재귀 단계마다 현재 문자열을 해시맵에 n번째임을 기록하기 위한 함수

1. 매개변수로 현재 재귀 단계 level과 현재까지 완성된 단어 str을 입력받는다.
2. 재귀가 최소 한번이라도 진행되었다면, 현재 단어가 dic에 있는지 체크하고 없다면 idx를 전위증가하여 기록해준다.
3. 단어의 최대 길이는 5이므로 기저조건으로 재귀 레벨이 5가 되었다면 리턴해준다.
4. 5번의 for문을 개행하고, 재귀 단계 1증가, str에 s의 i번째 단어를 더해주어 재귀를 진행해 준다.

 

문제풀이

1. bt함수에 level = 0, str = ""을 통해 백트래킹을 진행해 준다.
2. word를 key로 갖는 dic의 value를 answer로 저장해 준다.
3. answer를 리턴해 준다.

 

참고 사항

각 모음이 중복이 가능하므로 방문처리를 해주면 안된다.

 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

unordered_map<string, int> dic;
string s = "AEIOU";
int idx;

void bt(int level, string str) {
    if (level && !dic[str]) dic[str] = ++idx;
    if (level == 5) return;
    
    for (int i = 0; i < 5; i++) {
        bt(level + 1, str + s[i]);
    }
}

int solution(string word) {
    int answer = 0;
    
    bt(0, "");
    answer = dic[word];
    
    return answer;
}