[프로그래머스/Python] N으로 표현 - Level3

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

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

이 문제의 로직은 다음과 같다.

1. 숫자 N을 사용하는 숫자당 만들 수 있는 숫자 조합을 만든다.

2. 만들어진 숫자 조합에 number이 있으면 리턴한다.

3. 만들어진 숫자 조합에 없다면 1-2번 과정을 반복한다.

 

N이 5인 경우를 생각해보자.

 

숫자 5를 1번 사용할 때

5

숫자 5를 2번 사용할 때

55 (이어붙이는 경우) 5+5(10), 5-5(0), 5*5(25), 5/5(1)

숫자 5를 3번 사용할 때

555 (이어붙이는 경우) 5+55(60), 5-55(-50), 5*55(275), 5/55(1/11) 5+(5+5)(15), 5-(5+5)(5), 5*(5+5)(50), 5/(5+5)(0.5) ...

이렇게 조합을 생각하다 보면 패턴을 찾을 수 있다.

2번 사용하는 조합 = 1번 사용하는 조합과 1번 사용하는 조합의 사칙연산

3번 사용하는 조합 = 1번 사용하는 조합과 2번 사용하는 조합의 사칙연산

따라서, 숫자 N을 사용한 조합을 만들고 싶다면 해당 숫자를 만들 수 있는 조합끼리 사칙연산을 하면 된다.

 

def solution(N, number):
    num = [] # 숫자 조합을 담는 리스트
    
    for i in range(1, 9): # i = 숫자 N을 사용하는 횟수
        case = {int(str(N)*i)} # i번 사용하는 숫자 조합, 이어붙이는 경우의 수를 미리 넣어둠
        
        # 숫자 조합끼리의 사칙연산
        for j in range(0, i-1):  
            for x in num[j]:
                for y in num[-j-1]:
                    case.add(x+y)
                    case.add(x-y)
                    case.add(x*y)
                    if y != 0:
                        case.add(x//y)
               
        # 숫자 조합에 number 가 있는 경우
        if number in case:
            return i
        
        # 숫자 조합에 number 가 없으면 리스트에 추가
        num.append(case)
        
    return -1