[Python3]프로그래머스_N으로 표현

문제출처: https://programmers.co.kr/learn/courses/30/lessons/42895

접근법

문제는 이해하기 쉬웠다. 숫자 하나만 사용하여 타겟넘버를 만드는 것이다.
처음에 힘들었던 점은 괄호가 있다는 사실이였다. 그래서 dfs처럼 모든 괄호 및 사칙연산의 조합을 탐색하여 결과를 만들어내보려 했으나 이는 시간복잡도가 6(+,-,*,/,(,))의 제곱수로 증가하기 때문에 다른방법을 생각하려고 했다.
다른 방법을 모색하면서 생각한 점
1. 괄호로 둘러쌓인 연산들도 결국 숫자 N을 k번 사용하여 만든 결과이다.
2. 숫자 N=5일 때 5를 한번 사용한 경우 (5)와 같이 괄호로 쌓인 형태로 생각해도 된다.
3. 숫자 N을 k번 사용하여 만들 수 있는 숫자들은 아래의 경우 중 하나에 속한다.

• 숫자 N 1번 사용한 경우의 숫자 중 하나 + 사칙연산 + 숫자 N을 k-1번 사용한 경우의 숫자 중 하나
• 숫자 N 2번 사용한 경우의 숫자 중 하나 + 사칙연산 + 숫자 N을 k-2번 사용한 경우의 숫자 중 하나
  ...
• 숫자 N k-1번 사용한 경우의 숫자 중 하나 + 사칙연산 + 숫자 N을 1번 사용한 경우의 숫자 중 하나

• 마지막 코드에 통과하지 못한 예외케이스
  -> 숫자 N만 사용하여 사칙연산 없이 완성할 수 있는 경우를 고려하지 않았다.

코드

from collections import defaultdict
def solution(N, number):
    answer = 0
    d = defaultdict(set)
    for i in range(1,9):
        d[i].add( int(str(N)*i) )
        if( number in d[i] ): 
            return i
                 
    for i in range(2,9):
        for j in range(1,i):
            n1,n2 = j,i-j
            for n in d[n1]:
                for m in d[n2]:
                    d[i].add( n+m )
                    d[i].add( n-m )
                    d[i].add( n*m )
                    if( m!= 0 ):
                        d[i].add ( n//m )
        if( number in d[i] ):
            answer = i
            break
    return answer or -1