[프로그래머스/동적계획법/Lv.3] N으로 표현

문제 설명

 

코드

#include <string>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;


int solution(int N, int number) {
    int answer = -1;
    
    const int MIN = 8;
    vector<set<int>> v(MIN);
    string s="";
    
    for(auto &x : v){
        s+=to_string(N);
        x.insert(stoi(s));
    }
    
    for(int i=1;i<MIN;i++){
        for(int j=0;j<i;j++){
            for(auto x : v[j]){
                for(auto y : v[i-j-1]){
                    v[i].insert(x+y);
                    v[i].insert(x-y);
                    v[i].insert(x*y);
                    if (y != 0)
                        v[i].insert(x/y);
                }
            }
        }
        if(v[i].find(number) != v[i].end()) return i+1;
    }
    return answer;
}

 

소감

이 문제에 대한 풀이를 검색하다가 처음으로 set을 활용하게 되었다. 아래는 set에 대한 설명이 깔끔하게 되어 있는 블로그이다.

https://blockdmask.tistory.com/79
set은 기본적으로 원소를 자동 정렬해주고, 중복 key값은 허용하지 않는다.
따라서 (문제 조건으로 중복 값이 없다는 가정 하에) 어떤 key값이 있는지 찾는 데에 일반적인 container보다 훨씬 유리하다.

 

작성한 코드는 아래 블로그에서 참고한 내용이다.

https://gurumee92.tistory.com/164
올려주신 알고리즘을 읽고 코드를 짜다 보니 거의 베껴진 코드가 되고 말았다.
또한 set가 vector보다 더 적절한 것 같아서 수정했다.
실제로 실행시간을 비교해 보니 set는 20ms이내, vector는 50ms 이상으로 나왔다.
그 외에 다른 이유가 있을까 싶어 질문 댓글을 남겨두었다.