찬우의 이것저것 Chanwoo's blog

[프로그래머스 python]n으로 표현

2020-04-12

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

N number return
5 12 4
2 11 3

N을 x개 사용해서 number를 만들때 가장 적게 사용한 수를 구하는 문제이다.

처음엔 DP문제인지도 모르고 단순하게 문자열로 식을 만들어서 답을 구하는 아주 무식한 방법으로 접근했다.

"""
https://programmers.co.kr/learn/courses/30/lessons/42895?language=python3#
Programmers 42895 N으로 표현

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5+5 (+5 -5 *5 //5 5)
5-5
5*5
5//5
55

"""

from collections import deque


def get_value(expr: str) -> int:
    operations = ['+', '-', '*', '/']
    nums = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
    op_flag = True

    numbers = []
    opers = []
    value = 0

    for c in expr:
        if c in operations:
            op_flag = True
            opers.append(c)

        elif c in nums:
            if op_flag:
                numbers.append(c)
            else:
                numbers.append(numbers.pop(-1) + c)
            op_flag = False
        else:
            print('oper error')
            return -1

    value = int(numbers[0])
    for n, o in zip(numbers[1:], opers):
        n = int(n)

        if o == operations[0]:
            value += n
        elif o == operations[1]:
            value -= n
        elif o == operations[2]:
            value *= n
        elif o == operations[3]:
            value = value // n
        else:
            print('oper error')
            value = -1
            return -1
    return value


def make_expr(N, target) -> int:
    q = deque(N)
    visit = deque()
    MAX_COUNT = 8
    count = 0

    while q:

        curr = q.popleft()

        # if get_value(curr) == target:
        if eval(curr) == target:
            print(curr)
            return curr.count(N)

        if curr not in visit:
            if curr.count(N) > MAX_COUNT:
                break
            visit.append(curr)
            q.append(curr + "+" + N)
            q.append(curr + "-" + N)
            q.append(curr + "*" + N)
            q.append(curr + "/" + N)
            q.append(curr + N)

    return -1


def solution(N, number):
    N = str(N)
    return make_expr(N, number)


# case 1
N, number = 5, 12

# case 2
# N, number = 5, 31168


# N, number = 5, 24


print(solution(N, number))

아 문자열을 하나씩도니까 실행하는데 막 30초씩 걸린다.. 아.. 이건 아니구나를 너무 늦게 깨달았다.

값만 저장해서 푸는 방식으로 접근해보았다.

[5]

[10, 0, 25, 1, 55]

[15, 5, 50, 2, 5, -5, 0, 0, 30, 20, 125, 5, 6, -4, 5, 0, 60, 50, 275, 11, 555]

뭔가 나오는듯한데 이상하다. 만들수있어야되는데 라고 생각하는데 안되는게 있다.

앞에서부터만 계산하다보니 모든 경우의 수를 생각하지 못한것같다.


def solution(N, number):
    MAX_COUNT = 9

    value = [[] for _ in range(MAX_COUNT)]

    for i in range(1, MAX_COUNT):
        value[i].append(int(str(N) * i))
        for j in range(1, i):
            for a in value[j]:
                for b in value[i - j]:
                    value[i].append(a + b)
                    value[i].append(a - b)
                    value[i].append(a * b)
                    if b != 0:
                        value[i].append(a // b)

        if number in value[i]:
            return i

    return -1


# case 1 ans = 4
N, number = 5, 12

# case 2 ans = -1
# N, number = 5, 31168

# case 3 ans = 3
# N, number = 5, 4

# case 4 ans = 4
# N, number = 5, 54

print(solution(N, number))

Related Posts