[C++] 5주차 위클리문제 사전모음 84512

📌사전모음

/* 해당 문제 설명은 링크로 대체한다. */

📌풀이

처음에 문제를 읽고 이게 무슨 말이야 싶었다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
질문하기에 어떤 분이 달아주신 댓글 덕에 이해했는데 ... ㅎ........
아래와 같이 문자가 만들어지는 방식이다.

A
AA
AAA
AAAA
AAAAA
AAAAE
AAAAI
AAAAO
AAAAU
AAAE
...

여기서 공식을 이용하면 쉽게 풀어낼 수 있을 것 같은데 나의 경우 공식을 찾다가 못찾겠어서
결국 재귀함수로 돌면서 set에 담았고, set을 돌면서 word와 같을 경우 idx를 반환하는 식으로 풀었다.

📌코드

#include <string>
#include <vector>
#include <set>
using namespace std;

vector<string> v = {"A","E","I","O","U"};
set<string> s; //중복을 제거하고 담아 둘 변수

//v로 만들 수 있는 모든 조합을 s에 담음
void init(string str) {
    if(str.size()>5) return;
    s.insert(str);

    for(int i = 0; i < 5; i++) 
        init(str + v[i]);
}

int solution(string word) {
    int answer = 0;

    for(int i = 0; i < 5; i++) 
        init(v[i]);

    //s를 돌면서 word랑 일치하는 값을 찾아 idx 반환
    int idx=1;
    for(auto it = s.begin(); it!=s.end(); it++){
        if(*it == word) 
            return idx;

        idx++;
    }

    return -1; //몾찾은 경우
}

---

회고
확실히 이 방법으로 푸니 모두 1분 가량 정도 걸리는 걸로 측정됐다.
코드 자체는 깔끔하게 작성할 수 있어 좋았는데, 시간을 줄이려면 저장하지 않고 찾는 방법을 찾아봐야 같다.
다른 사람 풀이 중 엄청난 분이 계시긴 했다 .... 시간 복잡도와 공간 복잡도를 모두 고려한.......
그 분은 대체 ... 무..엇. ....취미로 푸시나요 혹시 ...? 이미 완성된 개발자 ..? 아니실까