[프로그래머스] N으로 표현(Python)

이거 푼 사람들은 쉽다고 하던데... 나는 못 풀어서 포스팅에 있는 글을 봤다.

1. 요약

숫자 N이 주어졌을 때, 피연산자로 N, NN, NNN, NNNN, ...을 활용 할 수 있다. 원하는 피연산자들을 선택하고, 사칙연산(+, -, *, /)을 하여 number을 구할 때, N사용 횟수를 최소로 해야한다.(i.e. 피연산자들을 하나로 이어 붙였을 때, 길이가 가장 짧은 것)

2. 아이디어

N의 사용횟수를 리스트의 인덱스로 사용하고, 사칙연산 결과들을 리스트에 저장한다.

pos = []
1개의 N으로 표현 할 수 있는 숫자 -> pos[0] = [N]
2개의 N으로 사칙연산하여 나온 숫자들 -> pos[1] = [N+N, N/N, N-N, N*N, NN]
3개의 N으로 사칙연산하여 나온 숫자들 -> pos[2] = [N+N+N, N*N/N, ..., NNN]
4개의 N으로 사칙연산하여 나온 숫자들 -> pos[3] = [N+N+N+N, N-N+N*N, ..., NNNN]
...
8개의 N으로 사칙연산하여 표현 할 수 있는 숫자들 -> pos[7] = [..., NNNNNNNN]


반복문을 돌면서, number을 찾으면 인덱스+1를 반환한다.

위의 예시를 구체적으로 확인하기 위해, 4개의 N으로 사칙연산하여 나온 숫자들을 살펴보자.
사칙연산에 사용되는 피연산자들을 []을 이용하여 표현하면, [N, KKK], [NN, KK], [KKK, N], [NNNN]이 나오고, KK, KKK의 정의는 아래와 같다.

KK: 2개의 N으로 사칙연산하여 나온 숫자들
KKK: 3개의 N으로 사칙연산하여 나온 숫자들

여기서, KK, KKK는 이전의 사칙연산에서 나온 결과들인데, 이들을 재활용하는 것을 확인 할 수 있다. 이를 토대로 구현하면 된다.

3. 코드

def solution(N, number):
    if number == N: return 1

    answer = -1

    # pos = [{N}, {NN}, {NNN}, ..., {NNNNNNNN}]
    pos = [set([int(str(N) * i)]) for i in range(1, 9)]
    pos_len = len(pos)

    for i in range(1, pos_len):
        for j in range(i):
            for op1 in pos[j]:
                for op2 in pos[i-j-1]:
                    pos[i].add(op1+op2)
                    pos[i].add(op1-op2)
                    pos[i].add(op2-op1)
                    pos[i].add(op1*op2)

                    if op2 != 0: pos[i].add(op1//op2)
                
        if number in pos[i]:
            answer = i + 1
            break

    return answer