[프로그래머스] level 3 - N으로 표현 (C++)

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

 

문제풀이

처음엔 동적계획법 문제라길래 number를 인수분해하고 그 인수들의 값을 계속해서 구하는 형식의 DP인줄 알았는데, 예시를 보니 인수분해로 접근하는 문제는 전혀 아닐 듯 싶어 미궁에 빠졌었다...

한 3일 정도를 궁리하다가 결국 모르겠어서 힌트를 본 결과, N을 8번까지 써서 구할 수 있는 모든 조합을 구하고 그 속에서 number를 찾는다는 것이었다.

 

솔직히 요즘 풀이할때 시간복잡도를 고려하면서 풀어야 한다는 강박에 시달리다보니 모든 경우의 수를 계산하는 방법은 고려도 안하고 있었는데.. 이번 문제를 풀면서 또 생각이 달라지게 되었다. 열린생각을 갖자...

 

아무튼 내가 풀이한 방식은 완성된 숫자를 담을 map과 dp값을 담을 2중 벡터를 사용하는 것이었는데 map의 key는 만든 숫자, value는 N을 사용한 횟수를 나타낸다.

 

처음에 N을 나열하여 만들 수 있는 숫자를 먼저 넣어주고, 본격적으로 dp를 활용한 반복문을 시작한다.

숫자를 만들때 사칙연산만 사용해야 한다는 규칙이 있는데, 이를 동적계획법과 연관지으면 N을 2번 사용하여 나타낸 숫자는 결국 N을 1번 사용한 숫자의 사칙연산이다.

또한 N을 3번 사용하여 만드는 숫자는 N을 한번 사용한 숫자와 N을 2번사용한 숫자의 사칙연산이다.

 

이 점에 착안하여 반복문을 만들면 N을 i번(i<9) 사용하여 나타낸 숫자를 구하기 위해 N을 각각 j번(j<i), i-j번 사용한 숫자들의 사칙연산을 수행하면 된다. 이때 j가 i/2를 넘어서면 똑같은 사칙연산을 두번 수행하게 되므로 j의 범위를 제한하고, 숫자의 순서가 바뀌면 값도 바뀌는 연산인 빼기와 나누기만 한번씩 더 수행하는 것으로 표현했다. 

 

i개의 N으로 나타낼 수 있는 모든 숫자를 구한 후에는 map에 담긴 숫자 중 우리가 구하려는 number가 있는지 확인하고, 아직 없다면 다음 반복으로 넘어가 i+1개로 나타낼 수 있는 숫자를 구한다. 모든 반복을 수행한 후에도 없다면 -1을 반환한다.

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(int N, int number) {
    
    map<int, int> numbers;
    vector<vector<int>> dp(9,vector<int>()); // 인덱스는 1~8을 사용
    map<int, int>::iterator iter;

    string n = "";
    for (int i = 1; i < 9; i++) { // n, nn, nnn ... 집어넣기
        n += "1";
        dp[i].push_back(N * stoi(n));
        numbers.insert({ dp[i][0], i });
    }
    
    for (int i = 2; i < 9; i++) { // N의 최대개수인 8개까지 반복
        for (int j = 1; j <= i / 2; j++) { // 더해서 i가 되는 두 숫자쌍의 개수만큼 반복
            for (int k = 0; k < dp[j].size(); k++) { // j와 i-j의 사칙연산
                for (int m = 0; m < dp[i - j].size(); m++) {
                    if (dp[i - j][m] == 0 || dp[j][k] == 0) continue;

                    dp[i].push_back(dp[j][k] + dp[i - j][m]);
                    dp[i].push_back(dp[j][k] - dp[i - j][m]);
                    dp[i].push_back(dp[j][k] * dp[i - j][m]);
                    dp[i].push_back(dp[j][k] / dp[i - j][m]);
                    dp[i].push_back(dp[i-j][m] / dp[j][k]);
                    dp[i].push_back(dp[i - j][m] - dp[j][k]);

                    for (int p = dp[i].size() - 7; p < dp[i].size(); p++) {
                        numbers.insert({ dp[i][p], i }); // 한번에 집어넣기
                    }
                }
            }
        }
        iter = numbers.find(number); // number가 만들어졌다면 다음 반복 없이 종료
        if (iter != numbers.end()) return iter->second;
    }
    return -1;
}

 

풀고난 뒤 다른사람들의 코드를 보며 생각한 개선할 점은, number와 같은 숫자를 만들었는지 확인하는 간격이 너무 커서 불필요한 연산을 수행하게 되는 것 이었다.

map의 find 연산이 다른 연산보다 오래 걸릴 것 같아 i의 연산을 모두 마치고 난 다음에 검사했는데, 사실 map 을 사용하는 것이 아니라 함수 등을 사용했다면 한번 구할때마다 number와 비교할 수 있으니 연산을 비교적 덜 수행해도 되지 않을까 하는 생각이 들었다.

물론 나는 함수 호출과 map의 find 연산 중 어떤것이 더 시간복잡도가 높은지 모르기 때문에... 어떤 방법이 더 좋은 것인지 아직 확실하지 않다. 좀 더 찾아봐야 겠다.

 

++ 오늘 배운 map

• find 연산 - iterator로 접근하여 찾는 key값이 있을 경우 해당하는 반복자를 반환한다. value에는 iter->second 로 접근할 수 있다.
• map.insert() 는 pair<>를 집어넣는 연산이기 때문에 값을 넣을때 중괄호로 감싸 넣어줘야 한다. 혹은 make_pair를 사용한다.
• map.insert() 는 이미 존재하는 key값을 중복하여 넣으면 삽입에 실패하고 해당하는 iterator와 false 값을 반환한다.