[알고리즘] 프로그래머스 - N으로 표현

프로그래머스 - N으로 표현

다른 사람 풀이 1

def solution(N, number):
    if  N == number:
        return 1
    S = [set() for x in range(8)]
    for i,x in enumerate(S, start=1): # start는 i의 시작점이다
        x.add(int(str(N)*i))

    for i in range(1, len(S)):
        for j in range(i):
            for op1 in S[j]:
                for op2 in S[i-j-1]:
                    S[i].add(op1 + op2)
                    S[i].add(op1 - op2)
                    S[i].add(op1 * op2)
                    if op2 != 0:
                        S[i].add(op1 // op2)
        if number in S[i]:
            return i + 1
    return -1

5를 이어 붙여 만든 조합을 제외하고 생각해 보면, N이 2인 숫자 조합을 만들기 위해서는 N이 1일때 경우의 수와 N이 1일때 경우의 수를 각각 사칙연산했다.
N이 3인 숫자 조합을 만들기 위해서는 N이 1일때 경우의 수와 N이 2일때 경우의 수를 각각 사칙연산했다.

즉, 특정 숫자만큼 5를 사용한 조합을 만들고 싶다면, 해당 숫자를 만들수 있는 덧셈 조합의 경우의 수 끼리 사칙연산을 해 주면 되는 것이다.

복잡하긴 하지만, N의 최대 수가 8이기 때문에 그리 많은 연산을 하지는 않을 것으로 보고 문제를 푼다.

설명 출처

다른 사람 풀이 2

def solution(N, number):
    possible_set = [0,[N]] # 조합으로 나올수 있는 가능한 숫자들, 여기에 계속 append하며 이후에 사용함
    if N == number: #주어진 숫자와 사용해야 하는 숫자가 같은 경우는 1개면 족하므로 1으로 놓는다.
        return 1
    for i in range(2, 9): # 2부터 8까지로 횟수를 늘려 간다.
        case_set = [] # 임시로 사용할 케이스 셋, 각 I 별로 셋을 만들어 possible set에 붙인다.
        basic_num = int(str(N)*i) # 같은 숫자 반복되는 거 하나를 추가한다.
        case_set.append(basic_num)
        for i_half in range(1, i//2+1): # 사용되는 숫자의 횟수를 구해야 하는데, 절반 이상으로 넘어가면 같은 결과만 나올 뿐이므로 절반까지만을 사용한다.
            for x in possible_set[i_half]:
                for y in possible_set[i-i_half]: # x와 y를 더하면 i 가 되도록 만든 수다.
                    case_set.append(x+y)# 각 사칙연산 결과를 더한다.
                    case_set.append(x-y)
                    case_set.append(y-x)
                    case_set.append(x*y)
                    if y !=0:
                        case_set.append(x/y)
                    if x !=0:
                        case_set.append(y/x)
            if number in case_set:
                return i
            possible_set.append(case_set) # 최종 결과물 set에 사칙 연산 결과를 더한다.
    return -1 #N 이 8까지 답이 없으면 -1을 출력한다.