프로그래머스 - N 으로 표현

programmers.co.kr/learn/courses/30/lessons/42895#

코딩테스트 연습 - N으로 표현

 

문제의 핵심은 N 을 최소의 갯수로 사용해서 number 를 찾아내는 것이다.

 

먼저, 입력 받은 N을 가지고 최대 8자리 수 까지 미리 만들어준다.

(문제에서 8자리를 넘으면 -1로 처리하도록 되어있으므로, 8자리까지만 생성)

 

unordered_set<int> s[MAX];
int base = 0;
    
for (int i = 0; i < MAX; ++i) {
    base = 10 * base + 1;
    s[i].insert(base * N);
}

 

 

 

unordered_set 을 사용한 것은, 첫번째로, 사칙연산으로 나타난 결과를 중복을 제거하면서 저장하기 위함이고 둘째로, 탐색시에 상수 시간이 소요되기 때문이다 (unordered_set 은 해시함수를 사용하기 때문에 시간복잡도 O(1) 임)

위 코드의 결과로 저장되는 값은

N = 1 일때, s[0] = 1, s[1] = 11, s[2] = 111, s[3] = 1111 ..... s[7] = 11111111 

N = 2 일때, s[0] = 2, s[1] = 22, s[2] = 222, s[3] = 2222 ..... s[7] = 22222222

.. 

N = 9 일때, s[0] = 9, s[1] = 99, s[2] = 999, s[3] = 9999 ...... s[9] = 99999999 이 된다.

 

 

number 가 한자리 수 인 경우, 별도의 사칙연산 필요 없이 단 한개의 N 만 사용하면 된다.

그러므로, 예외 처리를 위한 코드를 작성한다

 

if (number / 10 == 0) {
    if (s[0].count(number) > 0) {
        answer = 1;
        return answer;
    }
}

 

 

 

number 가 두자리수 이상인 경우, N 을 이어 붙인 것 외에도, 사칙연산을 한 결과도 필요하므로

다음과 같은 반복문을 사용해야 한다

 

for (int i = 1; i < MAX; ++i) {
    for (int j = 0; j < i; ++j) {
        for (auto op1 : s[j]) {
            for (auto op2 : s[i - j - 1]) {
                s[i].insert(op1 + op2);
                s[i].insert(op1 - op2);
                s[i].insert(op1 * op2);
                if (op2 != 0) s[i].insert(op1 / op2);
            }
        }
    }
    if (s[i].count(number) > 0) {
        answer = i + 1;
        break;
    }
}

 

 

 

i 는 사용한 N 의 갯수 - 1 을 의미한다. i = 2 이면 N 을 3개를 사용했다는 의미가 된다.

j 는 i 이전의 숫자들을 의미한다. i = 2 일때, N 을 3개를 사용해야 하는데, j 가 i 보다 작은 경우에만 N을 3개에 맞춰서 쓸수 있기 때문이다. j = 0 일때 1개의 N 을 사용하고, j = 1 일때 2 개의 N 을 사용한다. 예를들면, 22 + 2, 2 + 2 + 2 등이 해당한다.

사칙연산을 통해서 숫자들을 추가한 뒤에, i 번째에 찾고자하는 수 number 가 있다면, answer = i + 1 을 하여 리턴한다.

i 번째가 끝나가는 시점에 number 를 찾아서 answer 를 i + 1 로 잡는 것은, N 을 최소로 사용하기 위함이며, i + 1 인 것은 i 의 인덱스가 사용횟수보다 하나 적기 때문이다.

 

 

- c++

 

#include <unordered_set>
 
#define MAX 8
 
using namespace std;
 
int solution(int N, int number) {
    int answer = -1;
    
    unordered_set<int> s[MAX];
    int base = 0;
    
    for (int i = 0; i < MAX; ++i) {
        base = 10 * base + 1;
        s[i].insert(base * N);
    }
    
    if (number / 10 == 0) {
        if (s[0].count(number) > 0) {
            answer = 1;
            return answer;
        }
    }
    
    for (int i = 1; i < MAX; ++i) {
        for (int j = 0; j < i; ++j) {
            for (auto op1 : s[j]) {
                for (auto op2 : s[i - j - 1]) {
                    s[i].insert(op1 + op2);
                    s[i].insert(op1 - op2);
                    s[i].insert(op1 * op2);
                    if (op2 != 0) s[i].insert(op1 / op2);
                }
            }
        }
        if (s[i].count(number) > 0) {
            answer = i + 1;
            break;
        }
    }
    
    return answer;
}

 

 

 

 

 

개인적으로 알고리즘 중 dp 가 가장 어려운것 같다

이 코드도 순전히 내힘으로 푼 게 아닌 다른 사람들의 풀이를 보고 한 것이고

이런 생각들은 어떻게 하는지 볼 수록 놀랍다.