[Programmers] 위클리 챌린지 5주차 - 모음 사전

네 월요일은 위클리 챌린지의 날입니다. 오늘은 5주 차! 모음 사전을 보도록 하겠습니다.

 

https://programmers.co.kr/learn/courses/30/lessons/84512

코딩테스트 연습 - 5주차

 

위 링크에서 꼭 도전해보시고 오시길 바랍니다!

 

문제를 보면 A, E, I, O, U만을 사용하여 5자리의 단어까지 순서를 반환하는 문제입니다. 

 

이 문제를 공식을 찾아서 풀 수도 있습니다. 

 

word가 1자리라면, 5이내로 풀 수 있고, 2자리라면? 5 + 5*5 이내로 풀 수 있고... 하면 각각 word의 인덱스로부터 몇 번째 단어인지 파악할 수 있습니다.

 

하지만 저는 이 문제를 그냥 다 구했습니다.

 

이 문제의 최대 시간 복잡도는 몇일까요?

 

각 word의 자릿수를 1 2 3 4 5라 했을 때 각각 칸마다 5개~6개(비어있는경우)에 해당할 수 있으므로, 5 * 6 * 6 * 6 * 6 정도의 복잡도면 모든 수를 구할 수 있습니다.

 

set을 활용하여 자동으로 모든 수를 정렬한 뒤, 순서대로 탐색하면서 인덱스를 반환해주시면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
vector<string> v = {"A","E","I","O","U"};
set<string> s;
void makeword(string cur) {
    if(cur.size()>5) return;
    s.insert(cur);
    
    for(int i = 0; i < 5; i++) makeword(cur+v[i]);
}
int solution(string word) {
    int answer = 0;
    for(int i = 0; i < 5; i++) makeword(v[i]);
    
    int idx=0;
    for(auto it = s.begin(); it!=s.end(); it++, idx++) if(*it == word) { answer = idx+1; break; }; 
    return answer;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.