[코딩 테스트 연습(파이썬/Python)] 프로그래머스 _ N으로 표현

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

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

[문제 설명]

아래와 같이 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 함수를 작성하세요.

 

[제한 조건]

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

 

[아이디어]

1) N을 반복해서 써서 표현이 가능한 수는 반복하는 횟수가 최솟값에 해당한다.

(N=5라면 5,55,555,5555가 해당)

2) 나머지 수들에 대해서는 1개~8개를 조합하여 만들 수 있는 수들로 dp를 업데이트 해나가야한다.

3) 매번 dp[n]=k인 수들을 탐색해 찾아와야 하므로, 별도로 사전을 형성해 k개로 만들어지는 최소의 수들을 모아놓는 것이 필요해보인다.

4) 연산의 경우 [+, -, //, *]가 사용되는데, -와 //가 존재하므로 교환법칙이 성립하지 않는다.

 

# 통과
def solution(N, number):
    n = str(N)
    dp = [0] + [100]*32000; dp[N]=1
    d = dict(); t=['*','//','+','-']
    while int(n)<32000:
        d[len(n)] = d.get(len(n),set()) | {n}
        n+=n[0]
    for i in range(2,9):
        for j in range(1,i):
            for x in d[j]:
                for y in d[i-j]:
                    for v in t:
                        if 0<(a:=eval(x+v+y))<=32000:
                            dp[a] = min(i,dp[a])
                            if dp[a]==i:
                                d[i] = d.get(i,set())|{str(a)}
    k = 1
    while k<9:
        if str(number) in d[k]:
            return k
        k+=1
    return -1

처음 작성한 코드. 여유있게 통과되긴 하는데, 굳이 두 번에 반복문이 필요하다는 점과 구하는 답과 관계없이 매번 8까지의 모든 시행을 한다는 점, 몇 가지 불필요한 중복이 비효율적이다. 이에 아래처럼 코드를 조금 개선할 필요가 있었다.

 

# 개선
def solution(N, number):
    n = str(N)
    # dp 초기화
    dp = [0] + [100]*32000; 
    d = dict(); t=['*','//','+','-']
    # N의 단순 반복 채워놓기
    while int(n)<32000:
        d[len(n)] = d.get(len(n),set()) | {n}
        n+=n[0]
    # i개를 사용해 만들 수 있는 최소의 숫자들 모으기
    for i in range(1,9):
        for j in range(1,i):
            for x in d[j]:
                for y in d[i-j]:
                    for v in t:
                        if 0<(a:=eval(x+v+y))<=32000:
                            dp[a] = min(i,dp[a])
                            # dp를 업데이트 할 때만 사전에 추가
                            if dp[a]==i:
                                d[i] = d.get(i,set())|{str(a)}
        if str(number) in d[i]:
            return i
    return -1

사실 사전 내에 숫자들을 모을 때 중복을 피하기 위해 dp를 사용하긴 했는데, 답만 구할 때는 dp를 꼭 따로 구성하지 않아도 될 것 같다.