[프로그래머스] N으로 표현 (파이썬 풀이)
https://school.programmers.co.kr/learn/courses/30/lessons/42895
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
아래와 같이 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번만 사용하여 표현할 수 있습니다.
제출 코드
def solution(N, number):
d = []
for i in range(1,9):
# 중복 제거를 위한 set 사용
temp = set()
# N을 단순히 이어붙였을 경우
temp.add(int(str(N)*i))
for j in range(i-1):
for x in d[j]:
for y in d[-j-1]:
temp.add(x+y)
temp.add(x*y)
temp.add(x-y)
if y != 0:
temp.add(x//y)
if number in temp:
return i
d.append(temp)
return -1N과 사칙연산으로 다른 숫자를 표현하는 경우를 생각해보자. 덧셈, 뺄셈, 곱셈, 나눗셈, 숫자이어붙이기(예 : 5 & 5 => 55)가 있다.
문제에서 N은 최대 8번까지 쓸 수 있다고 했으니 1~8개의 N을 사용해서 만들 수 있는 수의 집합 리스트를 만들고 그 집합에서 number가 처음 나오는 경우를 구하면 된다.
for j in range(i-1):
for x in d[j]:
for y in d[-j-1]:첫번째 줄의 for문은 N의 개수를 하나씩 늘려서 계산하기 위한 for문이다.
두번째 줄과 세번째 줄의 for문은 만약 j개의 N로 수를 표현한다고 했을 때,
(1개의 N으로 표현한 수) & (j-1개의 N으로 표현한 수)의 사칙연산,
(2개의 N으로 표현한 수) & (j-2개의 N으로 표현한 수)의 사칙연산,
...
( j-1개의 N으로 표현한 수) & (1개의 N으로 표현한 수)의 사칙연산,
이런 식으로 모든 경우의 수를 구하기 위한 for문이다.
뺄셈과 나눗셈은 순서가 중요하기 때문에 0부터 j까지 모두 계산한다.