링크 : https://school.programmers.co.kr/learn/courses/30/lessons/84512
문제 설명
"A", "E", "I", "O", "U" 5개 알파벳으로만 이루어진 길이 5 이하의 모든 단어가 적힌 사전이 있습니다.
사전의 첫 번째 단어는 "A"이고 그 다음은 "AA", 마지막 단어는 "UUUUU"입니다.
단어가 주어질 때 몇번째 단어인지 리턴하시오.
ex) "AAAAE" : 6, "I" : 1563
아이디어
완전탐색에 목록에 있는 문제로, 사전에 길이가 5*5*5*5*5 = 3125가지 밖에 안되기에 모든 조합을 미리 만들어두고 확인하는 것으로 해결할 수 있습니다. 보자마자 바로 완전탐색이라고 생각이 들도록 문제 크기를 잘 고려하는게 중요할 것 같습니다.
사전은 leaf까지 깊이가 5인 트리가 있다고 생각하고 A,E,I,O,U 순으로 재귀적으로 순회하며 번호를 체크하는 방식으로 구현했습니다. 어떻게 보면 이걸 그대로 트리로 잘 세팅하면 트라이랑 비슷한 형태인가 싶습니다.
코드
#include <bits/stdc++.h>
using namespace std;
map<string, int> dict;
int cnt = 0;
void MakeDict(vector<string> alphabets, string currentStr, int currentNum)
{
if(currentNum == 5) return;
for(auto alphabet : alphabets)
{
dict[currentStr + alphabet] = ++cnt;
MakeDict(alphabets, currentStr + alphabet, currentNum + 1);
}
}
int solution(string word) {
vector<string> alphabets = {"A", "E", "I", "O", "U"};
MakeDict(alphabets, "", 0);
return dict[word];
}
메모리: 4.14 MB, 시간: 1.21 ms
다른분들의 풀이를 보는데 781에서 5의 제곱으로 나누어 구하는 방법은 진짜 어떻게 한건지 궁금합니다..
'알고리즘' 카테고리의 다른 글
프로그래머스 - [1차]캐시 (0) | 2024.05.27 |
---|---|
프로그래머스 - PCCP 모의고사 2회 - 신입사원 교육 (0) | 2024.05.26 |
프로그래머스 - 과제 진행하기 (0) | 2024.05.08 |
프로그래머스 - 가장 많이 받은 선물 (0) | 2024.05.06 |
프로그래머스 - 등산코스 정하기 (0) | 2024.03.16 |