프로그래머스 [Lv. 3] N으로 표현 {언어 : Python} [다시 풀어 보기]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42895?language=python3

프로그래머스

정답 코드

def solution(N, number):
    if number == 1:
        return 1
    setLists = []
    
    answer = -1
    value = 0
    for count in range(1, 9):
        setList = set()
        countMinusOne = count - 1
        value += N * 10 ** (countMinusOne)
        setList.add(value)
        nextRange = countMinusOne // 2 + 1 if countMinusOne % 2 else countMinusOne // 2
        for i in range(nextRange):
            for num1 in setLists[i]:
                for num2 in setLists[-i-1]:
                    setList.add(num1+num2)
                    setList.add(num1*num2)
                    if num1 - num2 > 0:
                        setList.add(num1 - num2)
                    if num2 - num1 > 0:
                        setList.add(num2 - num1)
                    if num1 // num2 > 0:
                        setList.add(num1 // num2)
                    if num2 // num1 > 0:
                        setList.add(num2 // num1)
        if number in setList:
            answer = count
            break
        setLists.append(setList)
    
    return answer

풀이 방법

 

1. N을 반복해서 붙인 숫자를 계산하고, 최대 8번까지 가능한 연산을 수행한다.
2. 각 연산 횟수마다 만들 수 있는 숫자들을 집합에 저장한다.
3. 이전 단계에서 만든 숫자들끼리 덧셈, 뺄셈, 곱셈, 나눗셈을 통해 새로운 숫자를 생성한다.
4. 목표 숫자인 number를 만들 수 있는지 확인하고, 만들 수 있다면 그 때의 연산 횟수를 반환한다.
5. 목표 숫자를 만들 수 없는 경우 -1을 반환한다.

 

느낀점

• set를 동적계획법에 활용하는 방법을 배울 수 있었다.
• 자바스크립트에서는 아래와 같이 사용한다.

const useSet = new Set();
useSet.add(1) // add로 값 추가
useSet.delete(1) // delete로 제거
useSet.has("A") // 값이 있는지 확인 => 여기서는 false
useSet.add(1).add(2).add(3) // 이렇게 사용도 가능
useSet.size // 개수 파악 => 여기서는 3
useSet.clear() // 초기화