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

문제 설명

 

아래와 같이 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 합니다.

입출력 예

N	number	return
5	12	4
2	11	3

 

입출력 예 설명

 

예제 #1

문제에 나온 예와 같습니다.

 

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

 

출처

※ 공지 - 2020년 9월 3일 테스트케이스가 추가되었습니다.

 

풀이

 

import numpy as np

def solution(N, number):
    for i in range(7):
        if np.where(func(N, number, i) == number)[0].size != 0:
          return i+1
    return -1



def calc(a, b, op):
    if op == '+':
        return a + b
    if op == '-':
        return a - b
    if op == '//':
        return a // b
    if op == '*':
        return a * b


def func(N, number, cnt):
    if cnt == 0:
        return np.array([N])

    op = ['+', '-', '//', '*']
    arr = np.array([], dtype = int)
    before = func(N, number, cnt-1)
    
    arr = np.append(arr, np.core.defchararray.add(str(N), before[before>=0].astype(str)))
    arr = np.append(arr, np.core.defchararray.add(before.astype(str), str(N)))

    arr = arr.astype(int)

    for i in op:
      arr = np.append(arr, calc(N, before, i))
      arr = np.append(arr, calc(before, N, i))
    
    arr = np.unique(arr)

    return arr

 

진짜 바보같은 생각을 하고 열심히 코드를 짰다. 숫자 5개를 조합하는 방법으로 1개+4개 / 4개+1개 이런 경우만 생각했는데 당연히 2개+3개 / 3개+2개 / 1개+2개+2개 등 이런 경우도 있는걸 놓치고 있었다. 문제 5, 6, 7, 8번을 다 틀려서 생각하다가 잘못된걸 찾았다.

그리고 NN 형태로 생긴 숫자는 말 그대로 원래 숫자끼리만 붙일 수 있고 (연산)숫자 / 숫자(연산)이런 형태로는 붙일 수 없는데 이것까지 생각해서 코드 짜느라 시간도 조금 더 걸렸다ㅠ

 

1. N을 이어붙여서만 만들 수 있는 숫자를 빈 배열에 추가한다.

2. 각 단계의 숫자를 조합해서 각 단계별로 사칙연산을 수행한다(5단계 -> 1/4, 2/3, 3/2, 4/1)

3. 한 단계가 끝날때마다 입력받은 number가 배열 안에 있는지 확인한다.

 

이런식으로 접근하면 아주 간단하게 풀 수 있었다. 마지막에 숫자를 1개부터 8개까지 써야되는데 7개까지만 써서 잠깐 도 막혔었다..ㅎ 중간에 리스트에 중복 제거를 해주면 속도도 크게 빨라진다.

def solution(N, number):
    
    arr = [[] for i in range(10)]
    nn = ''
    for i in range(8):
        nn += str(N)
        arr[i].append(int(nn))
        for j in range(i):
            for k in arr[j]:
                for l in arr[i-j-1]:
                    arr[i].append(k + l)
                    arr[i].append(k - l)
                    arr[i].append(k * l)
                    if l != 0:
                        arr[i].append(k // l)
        arr[i] = list(set(arr[i]))
        if number in arr[i]:
            return i+1
    
    return -1

 

테스트 1 〉	통과 (0.99ms, 10.6MB)
테스트 2 〉	통과 (0.03ms, 10.4MB)
테스트 3 〉	통과 (0.05ms, 10.4MB)
테스트 4 〉	통과 (18.64ms, 14.4MB)
테스트 5 〉	통과 (14.78ms, 13.2MB)
테스트 6 〉	통과 (0.21ms, 10.4MB)
테스트 7 〉	통과 (0.20ms, 10.4MB)
테스트 8 〉	통과 (17.92ms, 14.5MB)
테스트 9 〉	통과 (0.03ms, 10.4MB)