[프로그래머스] N으로 표현 (파이썬)

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/42895

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

 

문제 풀이

 

정수 N 을 최소로 사용해서 K 를 만들어야한다.

최대 8번까지 N 을 사용 할 수 있고, 8번이 넘어갈 경우 -1 을 리턴하면 된다.

 

DP 를 사용해서 풀 수 있으며, N 을 1 번 사용했을 때, 2번 사용했을 때, 3번 사용했을 때 .... 8번 사용했을 때의 값들 중에서 K 가 있는지 확인하고

K 가 있으면 몇 번 사용했을때 K 가 나왔는지를 리턴하면 된다.

 

n 이라는 배열을 사용했고, n[i] 는 n 을 i 번 사용했을 때 나올 수 있는 모든 경우의 수들의 집합이다.

또한, 중복되는 숫자의 방지를 위해서 total 이라는 배열을 사용했으며, total 안에는 n 으로 만들 수 있는 모든 수가 들어간다.

 

예를들어 n 을 3번 사용해서 9 가 만들어지고, n 을 5 번 사용해서 9 가 만들어 지면 n 을 5 번 사용해서 만들어지는 9 는 n[5] 에 추가하지 않는다.

왜냐하면, target number 가 9 인 경우에 정답은 3이 되어야하는데 5로 나올 수 있는 혼동이 있을 수 있으며,

n[4] 에서 이미 9를 사용해 만든값이 n[6] 에서 중복으로 들어갈 수있는걸 방지하기 위해서이다.

 

중복처리를 간편하게 하기위해서 list 를 set 으로 바꾸어 차집합으로 계산했다.

또한 사칙연산 중 + 과 - 는 순서에 따라 그 값이 바뀌므로, 2번 처리해주었다.

예를 들어 n[3] 은 n[1] 과 n[2] 의 조합과 n[2] 와 n[1] 의 조합들로 이루어져있다.

시간 복잡도

n[i] = n[a] X n[i-a] | n[i-a] X n[a] 이다.

n[a] 의 원소의 개수를 k, n[i-a] 의 원소의 개수를 p 라고 두면, 총 경우의 수는 2 * 4 * k * p 이다.

 

이러한 계산을 i - 1 번 반복해야하므로, 총 계산 수는 (i - 1) * 2 * 4 * k * p 이다.

정확하게 시간 복잡도를 계산하기 어렵지만, Big(O) 는 지수함수 이상의 시간복잡도를 가지며, 다행히도 결과값의 최대값이 8이므로

시간초과를 피해 갈 수 있다.

  

소스 코드

def solution(N, number):
    total = [];
    n = [];
    for i in range(9):
        n.append([]);
    ans = 0;
    
    n[1].append(N);
    total.append(N);
    
    def cal(a,b):
        temp = [];
        s = n[a];
        f = n[b];
        for i in s:
            for k in f:
                temp.append(i + k);
                if k != 0:
                    temp.append(i // k);
                temp.append(i - k);
                temp.append(i * k);
        setTemp = set(temp);
        setTotal = set(total);
        ret = setTemp - setTotal;
        return list(ret);
        
    for i in range(2,9):
        n[i].append(int(str(N) * i));
        total.append(int(str(N) * i));
        for j in range(1,i + 1):
            a = j;
            b = i - j;
            ret = cal(a,b);
            total = list(set(total) | set(ret));
            n[i] = list(set(n[i]) | set(ret));
            ret = cal(b,a);
            total = list(set(total) | set(ret));
            n[i] = list(set(n[i]) | set(ret));
    if (number not in total):
        return -1;
    else:
        for i in range(1,9):
            if (number in n[i]):
                return i;