(Python) - 프로그래머스 : N으로 표현

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

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

 

• 해설 :

주어진 수 N을 사칙연산만으로 조합하여 targetNumber를 찾는데에 몇 번의 연산이 필요한지 찾는 문제이다.

 

 

 

• 풀이 :

사칙연산을 진행하며 나온 결괏값을 중복을 방지하기 위해 set 자료구조로 list에 append 한다. 이 결괏값 배열의 원소들에 반복적으로 N으로 사칙연산을 수행하여 targetNumber가 나올 때까지 횟수를 카운팅한다.

 

 

 

 

def solution(N, number):
    S = [0, {N}]
    if N == number:
        return 1
    for i in range(2, 9):
        case_set = {int(str(N)*i)}
        for i_half in range(1, i//2+1):
            for x in S[i_half]:
                for y in S[i-i_half]:
                    case_set.add(x+y)
                    case_set.add(x-y)
                    case_set.add(y-x)
                    case_set.add(x*y)
                    if x != 0:
                        case_set.add(y//x)
                    if y != 0:
                        case_set.add(x//y)
        if number in case_set:
            return i
        S.append(case_set)
    return -1