[출처] : https://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 합니다.
입출력 예
입출력 예 설명
예제 #1
문제에 나온 예와 같습니다.
예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.
접근
접근을 어떻게 해야될지 몰라서 구글링을 통해서 방법을 이해해서 코드를 짰다.
접근 방법은 완전탐색이다.
모든 경우의 수를 다 찾고, 중복을 제거하는 식으로 접근했다.
우선 N==number인경우는 단 한가지밖에 나올수 없다.
N과 사칙연산을 사용해서 number를 표현하라고 했는데, 두개가 같으면 그냥 그 자체인 하나밖에 나올수가 없다.
그 다음으로 처리해준것이 모든 연산결과를 저장하기 위한 집합자료형이 담긴 리스트를 만들었다.
이렇게 만든 이유는 N을 사용한 횟수-1을 인덱스로 하고, 각 경우에 나올수 있는 수를 다 넣어준다음, 목표로 하는 number를 찾아주기 위해서이다.
이때 set 사용한 이유는 다른 연산이지만, 같은 결과를 내는 것들이 존재하기 때문에 이를 제거하기 위해서 중복을 없애주는 set 자료형을 사용하였다.
(예를 들면 5+55, 55+5는 다른 연산이지만 같은 값이 나온다.)
아래와 같이 만들어 주었다.
operator_set = [set() for _ in range(8)]그 다음으로 사칙연산 없이 나올수 있는 N을 위에서 정의한 리스트에 각각 넣어주었다.
예를 들면 아래와 같다
1. 5를 1번 쓰는 경우 => 5
1. 5를 2번 쓰는 경우 => 55
1. 5를 3번 쓰는 경우 => 555
이런식으로 사칙연산을 통해서 만들수 없는 경우를 만들어서 리스트에 넣어주었다.
해당 코드는 아래와 같다.
(enumerate를 사용하면 인덱스와, 해당 iterator 객체의 값을 반환해준다.
이때 start값을 지정하면 인덱스가 1부터 시작한다 - 아래에서 인덱스는 a에 들어감)
for a,b in enumerate(operator_set,start=1):
b.add(int(str(N)*a))가장 중요한 부분이다.
이제 반복문을 돌면서 위에서 넣어준 리스트를 조합해서 모든 경우의 사칙연산을 진행할것이다.
원리는 이러하다.
N을 i번 사용한 값을 구한다고 가정하겠다.
- (N을 1번 사용한 값) (연산자 -
+,-,*,/) (N을 i-1번 사용한 값) - (N을 2번 사용한 값) (연산자 -
+,-,*,/) (N을 i-2번 사용한 값)
위에서 든 예시와 같이 N번을 i번 사용한 결과를 구하고 싶다 하면, 1부터 i-1번까지 돌면서(한쪽이 0번 사용하면 연산이 불가능) 연산자를 기준으로 한쪽에는 1부터 증가, 다른한쪽에는 i-1부터 감소하는 식으로 연산을 진행하도록 했다.
여기서 주의할 점은, 나누기 연산의 경우, 0으로 나눌수 없다는 점이고 이를 if문을 이용해서 처리해야된다.
N을 1번 사용했을때 나오는 경우의 수를 저장하는 리스트에 값이 저장이 되고, 이를 이용해서 2번 사용했을때, 3번 사용했을때....8번사용했을 때의 결과를 모두 구할수 있다.
즉, i번 사용했을때의 결과를 구하려면 1번부터 i-1번까지 사용했을때의 각각의 수가 필요하고 이를 토대로 i번 사용했을때를 구할수 있게된다.
이것은 dp의 메모이제이션과 동일하게 보일것이다.
그래서 이 문제의 유형이 dp인것이다.
문제에서 원하는 것은, 최소사용횟수이므로, 위에서 만든 N 사용횟수에 대한 결과를 저장하는 리스트를 앞에서 부터 돌면서, 원하는 값인 number를 찾게 되면 바로 반환해주면된다.
코드에서 i+1로 한 이유는 인덱스를 0부터 시작했기 때문이다.
최종 코드
def solution(N, number):
#N == number 이면 표현할수 있는 방법은 1가지임
if N == number:
return 1
#연산 셋을 저장할 집합 - 중복제거를 위해 집합사용
operator_set = [set() for _ in range(8)]
#각각 표시할수 있는 N의 수를 나열한다.
#주어진 조건에 의하면 최대 8번 까지 사용된다 - 8보다 크면 -1을 리턴하게 함.
#각각의경우 연산자 없이 만들어질수 있는 경우는 N=5로 가정하면 5,55,555....5555555이다
#이것들을 전부 각 set에 넣어줌(operator_set의 리스트를 하나씩 돌면서 set안에 넣음)
for a,b in enumerate(operator_set,start=1):
b.add(int(str(N)*a))
#반복문을 돈다
#i의 의미는 N을 사용한 횟수이다.
#operator_set[i]는 N을 i번 사용한 횟수이다.
for i in range(1,8):
#i = 1이면 0
#i = 2이면 0,1 이런식으로 반복하도록 함.
#이렇게 하는 이유는 그 아래 두 반복문에 있음
#만약 N을 3번 사용했다면 나올수 있는 가지수는 - (1,2),(1,1,1),(2,1)임
#이를 구현하기 위해서 operator1에는 operator_set에는 j를, operator2에는 i-j-1번째를 가져옴(인덱스를 0부터 사용하기 때문에 이렇게 함.)
#즉 N이 5이면 1번 사용했을떄와 4번 사용했을때의 식을 각각 사칙연산 , 2,3 / 3,2 / 4,1 이런식으로 진행함.
for j in range(i):
for operator1 in operator_set[j]:
for operator2 in operator_set[i-j-1]:
operator_set[i].add(operator1 + operator2)
operator_set[i].add(operator1 - operator2)
operator_set[i].add(operator1 * operator2)
if operator2 != 0:
operator_set[i].add(operator1 // operator2)
if number in operator_set[i]:
return i+1
#반복문을 다 돌때까지 없었다면 8보다 크다고 생각하고 -1
return -1결과
방법은 대충 생각했는데, 구현하는 능력이 부족해서 구글링을 했고, 구글링 한 내용도 한참을 봐서야 이해를 했다.
