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

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

프로그래머스

 

문제 요약

숫자 N만 사용 + 사칙 연산 사용 → number 만들기

경우가 여러 개인 경우, N을 최소로 사용하는 횟수

사용 횟수가 8보다 크면 -1 출력

 

코드 설명

 

기본적으로 특정 숫자 x를 N번 사용하는 '횟수'를 구해야 하기 때문에

횟수에 집중해서 생각해본다면, x를 N번 사용해서 만들 수 있는 숫자는

 

x..x (x를 n번)

x를 1번   (+ - * /)   x를 (n-1)번

x를 2번   (+ - * /)   x를 (n-2)번

.

.

.

x를 (n-1)번   (+ - * /)   x를 1번

 

으로 생각해볼 수 있다!

 

def solution(N, number):
    # s[i] : 주어진 수 N을 i + 1번 사용해서 만들 수 있는 수들의 집합
    s = [set() for x in range(8)]
    # 8개의 set 각각 초기화, s[0] = N, s[1] = NN ...
    for i, x in enumerate(s, start = 1):  # start 인자는 첫 번째 원소의 idx를 0이 아니라 1부터 시작하게 해준다
        x.add(int(str(N) * i))
    # s[i], N을 i+1개 사용했을 때 만들 수 있는 숫자 구하기
    for i in range(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]:
            answer = i + 1
            break
        else:
            answer = -1

    return answer

 

N을 i + 1번 사용해서 만들 수 있는 수들의 집합을 만들어준다.

 

각 집합을 사칙연산자 없이 만들 수 있는 숫자들로 초기화해준다

enumerate의 인자로 start = 1을 넣어주면, 인덱스를 0이 아닌 1부터 시작하게 할 수 있다.

 

특정 정수를 여러 번 이어붙이는 과정은 숫자를 정수로 다룰 때보다 문자로 다룰 때가 더 편하기 때문에

정수를 str()로 변환하여 곱하기 연산으로 쉽게 이어붙여주고, 다시 int()로 변환해준다.

 

N을 i+1개 사용했을 때 만들 수 있는 숫자들을 1개 사용했을 때부터 숫차적으로 구한다.

위에서 일반화한 내용을 이중 반복문을 사용해서 구현했다.

 

나누기 연산을 수행할 때에는 0으로 나누지 않도록 조건을 걸어서 처리해줘야 한다.

 

최소 N 사용 횟수를 구해야 함으로,

가장 밖의 반복문이 한 회 끝나기 전에 구하려는 number가 현 집합에 존재하는지 확인한다!

 

있다면 해당 횟수가 정답이므로 종료

없다면 answer를 -1로 유지한 채로 계속해서 진행

 

배운 점

- enumerate 함수를 사용할 때 start = 1 인자를 줌으로써, 인덱스를 1부터 시작하게 할 수 있다.

- 다이나믹 프로그래밍을 활용하여 코드를 짜려고 할 때, 어떤 내용(여기서는 횟수)에 집중해야 할 지를 생각해보자.

- 5번을 사용해서 만들 수 있는 숫자는, 더 적은 횟수(1번, 2번, 3번 ... )를 사용해서 만들 수 있는 숫자들을 사칙연산으로 계산한 숫자이다.

- 하지만 횟수에 따른 생성 가능한 숫자들을 만드는 것에서 그치는 것이 아니라, 목표 number를 만들 수 있는 최소 횟수를 구해야 한다.

- 따라서, 매 반복문마다 위의 내용을 확인하여 목표 숫자가 만들어졌다면 종료!

 

참고 자료

https://velog.io/@s2ul2/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4level3-N%EC%9C%BC%EB%A1%9C-%ED%91%9C%ED%98%84-Python%ED%8C%8C%EC%9D%B4%EC%8D%AC