[프로그래머스 풀이, 설명] N으로 표현 C++

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42895 

 

#include <string>
#include <vector>
#include <unordered_set>
#include <cmath>

using namespace std;

//k개의 N을 붙여 만든 하나의 숫자를 반환. 
int get_basic_number(int N, int cnt){
    int res = 0;
    while(cnt > 0){
        cnt--;
        res += N * pow(10, cnt);
    }
    return res;
}

int solution(int N, int number) {
    
    if(N == number) return 1;
    
    vector<unordered_set<int>> dp(9); 
    
    for(int k = 1; k <= 8; k++){

	//k개의 N을 쭉 붙여서 만든 숫자 NNNN 같은 걸 저장
        dp[k].insert(get_basic_number(N, k));

	//i개의 N을 붙여 만든 숫자와 j개의 N을 붙여 만든 숫자를 연산해서 총 k개의 N이 쓰인 숫자 생성
        for(int i = 1; i < k; i++){
            for(int j = 1; j < k; j++){
                if(i+j == k){
                    for(int a : dp[i]){
                        for(int b : dp[j]){
                            dp[k].insert(a+b);
                            if(a-b>0) dp[k].insert(a-b);
                            dp[k].insert(a*b);
                            if(a/b>0) dp[k].insert(a/b);
                        }
                    }
                }
            }
        }

        //k개의 숫자로 만든 값이 모인 dp[k]라는 set에 number랑 같은게 있는 지 탐색
        if(dp[k].find(number) != dp[k].end())
            return k;
    }
    return -1;
}

 

vector<unordered_set<int>> dp(9);

[ dp[k]가 뭔가? ]

• dp[k]는 unordered_set으로, N이 k번 쓰였을 때 나올 수 있는 모든 값들을 저장하는 집합.
• N이 최소 1번은 쓰여야 하니까 dp[0]은 비워두고, dp[1]부터 채우면 된다.
• N이 8개보다 더 많이 쓰이면 -1을 리턴하니까 최대 8개까지 쓰일 수 있으므로 dp의 인덱스는 1부터 8까지 사용한다.

 

[ dp[k]에는 어떤 값들이 들어갈까? ]

N이 k번 쓰이면서 생길 수 있는 값의 종류에는 크게 두 가지가 있다.

 

1. 그냥 k개의 N이 하나로 쭉 이어진 숫자.
   • 예를 들어 N이 5이고 k가 2이면 dp[2]에 55가 저장되고, k가 6이면 dp[6]에 555555가 저장됨.
   • 코드에서는 dp[k].insert(get_basic_number(N, k)); 로 구현되어 있다.
2. i개의 N으로 만들어진 숫자랑 j개의 N으로 만들어진 숫자가 무언가 연산이 되면서 총 k개의 N이 쓰였을 때의 그 결과값.(i+j==k)
   • 예를 들어 N이 5이고 k가 7일 때 dp[7]에는 이미 5555555가 있을 것이다. 그런데 이것 외에도 555랑 5555가 어떤 연산이 되어서 값을 낸다면 얘도 결과적으로 5가 7개 쓰인 거니까 dp[7]에 저장되어야 한다.
   • 코드에서는 if(i+j == k)를 통해 N이 i개 사용된 값과 N이 j개 사용된 값을 연산해서 총 k개가 쓰이는 경우를 탐색하도록 했다.
   그렇게 해서 결론적으로는 N이 k번 쓰여서 만들어진 숫자, i개 쓰인 숫자와 j개 쓰인 숫자를 연산해서 총 k개가 쓰인 결과값을 저장한다.

 

[ 기타 조건 : if(a-b>0), if(a/b > 0), set 대신 unordered_set을 쓰는 이유 ]

1. 후자를 계산할 때 a는 N이 i개 쓰여서 나온 값들 중 하나고, b는 N이 j개 쓰여서 나온 값들 중 하나인데 여기서 if(a-b>0)과 if(a/b > 0)을 넣은 이유는 입력조건에서 number가 1이상이기 때문이다. number랑 같은 애를 찾아야 하는 거니까 0보다 같거나 작은 애들은 dp에 추가할 필요가 없다.
2.  a/b를 할때 나누는 수 b가 0이 아닌지 조건을 따져야 하지 않나? 라고 생각할 수도 있는데, 애초에 a/b, a-b, a+b, a*b를 계산해서 dp에 넣을 때 0보다 큰 값일 때에만 넣었기 때문에 b에 들어오는 값이 0일 수가 없다. 그러니 이 조건도 필요 없다. (여기서 이 조건을 추가해도 맞긴 맞는데 굳이 안써도 되는 걸 쓸 필요는 없다. 쓰면 시간만 몇 ms 느려지더라.)
3. set은 오름차순으로 정렬하는데 unordered_set은 정렬하지 않는다. 여기선 정렬할 필요가 없고, 정렬하면 시간만 늘어나니까 unordered_set을 사용하는 게 더 효율적이다.