오늘은 프로그래머스의 N으로 표현을 풀어 보았다. 언어는 파이썬을 사용했다.
1. 문제 설명
아래와 같이 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 함수를 작성하세요.
1-1. 제한 사항
- N은 1 이상 9 이하입니다.
- number는 1 이상 32,000 이하입니다.
- 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
- 최솟값이 8보다 크면 -1을 return 합니다.
2. 다른 풀이
def solution(N, number):
# set(중복값을 가지지 않음)을 8개 생성
s = [set() for x in range(8)]
# 각 set에 N, NN, NNN ... 을 넣어줌
for i, x in enumerate(s, start=1):
x.add(int(str(N) * i))
# 1부터 8까지
for i in range(1, len(s)):
if number in s[0]:
answer=1
break
# 0부터 i까지
for j in range(i):
# j의 값들
for op1 in s[j]:
# j + (i-j-1) + 1 = i
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위 문제는 동적 계획법(Dynamic Programming)을 사용한 풀이법이다. 재귀적 함수처럼 매번 함수를 호출해서 계산을 하는 것이 아닌, 계산된 내용을 저장해두어 다음 계산에 활용하는 방식이다. 시간적인 효율성도 더 높다.
위 문제에서 알고리즘은 다음과 같다.
1. 최솟값이 8보다 크면 -1을 return하므로 리스트 s에 총 8개의 set()을 생성해준다.
2. 각 set()에 N, NN, NNN ... 과 같이 N을 i개 써서 만들 수 있는 숫자를 생성하여 넣어준다.
3. 작은 i(작은 set)부터 순환문을 돌린다. 이 과정에서 set j와 set i-j-1간의 모든 원소를 각각 사칙연산을 하고 s[i]에 넣어준다.
쉽게 이야기해서 N을 2개를 사용한 집합을 만들기 위해서는 N을 1개 사용한 집합과 1개 사용한 집합을 각각 +, - , *, / 를 해주면 된다.
한 가지 더 예시를 들면 N이 4개 사용한 숫자들의 집합을 만들기 위해서는
(N 사용 횟수, N 사용 횟수) = (1, 3), (2, 2), (3, 1) 간의 사칙연산을 해주면 구할 수 있다.
- 각각의 집합을 구할 때마다 number가 존재하면 answer = i + 1이 된다.(리스트 s에서 i는 0부터 시작하기 때문)
- 여기서 하나 확인해야하는 것은 첫 반복문을 보면 i = 1부터 시작하는데 number가 s[i]에 존재하는 경우를 고려해야한다.(예외사항을 잘 체크하는 실력을 키워야 한다.)
아무튼
동적 계획법을 구현하는 것은 손으로 쓰면서 하는 것이 가장 중요할 것 같다. 단순히 머리 속으로 구현하기에는 어려웠다. 작은 것부터 규칙을 찾아 나가는 것이 중요한 듯 하다. 어렵긴해도 성공하면 재밌을 것 같다.
