[프로그래머스] N으로 표현 (python)
문제설명
문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42895
Idea 01
유의미한 풀이 규칙을 찾을 수 없어 다른 분의 접근 방법을 참고했습니다. (참고 블로그)
주어진 N은 2, number이 11일 때 return 3을 구할 수 있는 횟수(n)를 구하는 방법은 다음과 같습니다.
n이 1일 때는 딱 1개만 만들 수 있습니다.
n이 2일 때는 2를 2번 이어붙인 경우와, 2를 1번(n-1) 사용했을 때 값에서 2를 사칙연산한 경우가 존재합니다.
n이 3일 때는 2를 3번 이어붙인 경우와, 2를 2번(n-1) 사용했을 때 값에서 2를 사칙연산한 경우가 존재합니다.
N=2일 때, number=11을 만족하는 식은 22/2=11이고 이때 2가 최소 3번 사용된 걸 확인할 수 있습니다.
위 방법을 통한 풀이를 하기 위해서는 2를 이어붙이는 경우를 제외하곤
n이 2인 숫자 조합을 만들기 위해선 2를 1번(n-1) 사용했을 때 값과 2를 사칙연산합니다.
n이 3인 숫자 조합을 만들기 위해선 2를 2번(n-1) 사용했을 때 값과 2를 사칙연산합니다.
특정 N에 대한 최소 조합을 구하기 위해선 n-1값에 N을 사칙연산하면 최소 n을 구할 수 있는 것으로 보이지만, 단순하게 n-1 숫자 조합에서 N을 사칙연산하는 방법으로는 최소횟수를 제대로 구할 수 없습니다.
N=4일 때 number=3을 만족하는 최소 식은 4-(4/4)이지만, 위의 접근 방법을 사용하면 4에서 (4/4)를 빼주는 경우는 없습니다. (숫자조합이 (2+2)라면 여기에 2를 +, - ,*, / 만 진행하기 때문)
Idea 02
위에서 발생한 예외(4-(4/4))를 처리하기 위해 다른 분의 접근 방법을 참고했습니다. (참고블로그)우선 N=4일 때, 숫자 4를 최소 1~8번 조합할 수 있습니다. (문제에서 최소 사용 횟수를 8까지 정의)
4를 2번 사용해서 만들 수 있는 경우이며, 이 때 숫자 2에 대한 사칙 덧셈을 표현하면 다음과 같습니다.
2 = 2 + 0
= 1 + 1
위 사칙 덧셈을 참고하여 4를 2번 사용해서 만들 수 있는 경우의 수를 아래와 같이 정의할 수 있습니다.
4를 2번 이어붙인 경우 (2+0) U
4를 1번 사용한 경우와 4를 1번 사용한 경우의 사칙연산 값 (1+1)
4를 3번 사용해서 만들 수 있는 경우 중, 앞, 뒤 연산에 대한 자리가 바뀌어도 같은 값을 가지는 경우는 "-"로 표현했으며, 이 때 숫자 3에 대한 사칙 덧셈을 표현하면 다음과 같습니다.
3 = 3 + 0
= 1 + 2
= 2 + 1
위 사칙 덧셈을 참고하여 4를 3번 사용해서 만들 수 있는 경우의 수를 아래와 같이 정의할 수 있습니다.
4를 3번 이어붙인 경우 (3+0) U
4를 1번 사용한 경우와 4를 2번 사용한 경우의 사칙연산 값 (1+2) U
4를 2번 사용한 경우와 4를 1번 사용한 경우의 사칙연산 값 (2+1)
즉, 위에서 구한 규칙을 숫자 N에 대해서 n번 사용할 경우 사칙 덧셈으로 표현하면 다음과 같습니다.
N = N + 0 = 1 + N-1위 사칙 덧셈을 참고하여 N을 n번 사용해서 만들 수 있는 경우의 수를 아래와 같이 정의할 수 있습니다.
= 2 + N-2
= N-1 + N-N-1
N을 n번 이어붙인 경우 (N+0) U N을 1번 사용한 경우와 N을 N-1번 사용한 경우의 사칙연산 값 (1+N-1) U N을 2번 사용한 경우와 N을 N-2번 사용한 경우의 사칙연산 값 (2+N-2) U N을 N-1번 사용한 경우와 N을 N-N-1번 사용한 경우의 사칙연산 값
위와 같이 N을 n번 사용할 수 있는 모든 경우의 수를 구하여 최소 N을 사용한 number을 찾아낼 수 있습니다.
Solution 01
def solution(N, number):
if N == number:
return 1
global_stack = [set([int(str(N)*(i+1))]) for i in range(8)]
for i in range(1, 8):
for j in range(i):
for n1 in global_stack[j]:
for n2 in global_stack[i-j-1]:
global_stack[i].add(n1 + n2)
global_stack[i].add(n1 - n2)
global_stack[i].add(n1 * n2)
if n2 != 0:
global_stack[i].add(n1 // n2)
if number in global_stack[i]:
return i+1
return -1
N을 n번 사용하여 구할 수 있는 모든 경우의 수 중, number을 만족하는 n의 최소 횟수를 구하는 코드입니다.
만약 N이 3이라 가정하면 3의 사칙 덧셈에 해당하는 2+1일 때와 1+2을 각각 구하고 있습니다.
이때 사칙연산 종류에 따라 똑같은 값을 중복되게 구하고 있습니다. (n1=(2+2), n2=2일 때와 n1=2, n2=(2+2)인 경우 등)
Solution 01은 같은 값을 중복되게 계산하기 때문에 효율적이라고 볼 수 없습니다.
Solution 02
if N == number:
return 1
stack = [{N}]
for i in range(1, 8):
nums = set([int(str(N)*(i+1))])
for j in range(i//2+1):
for n1 in stack[j]:
for n2 in stack[i-j-1]:
nums.add(n1 + n2)
nums.add(n1 * n2)
nums.add(n1 - n2)
nums.add(n2 - n1)
if n2 != 0:
nums.add(n1 // n2)
if n1 != 0:
nums.add(n2 // n1)
if number in nums:
return i+1
stack.append(nums)
return -1
사칙 연산에서 결과 값이 바뀔 수 있는 경우는 -와 /가 있습니다. (1-2, 2-1, 1/2, 2/1이 다르기 때문)
-와 /인 경우 n1, n2와 n2, n1 순서로 값을 구합니다.
마지막으로 i//2+1을 한 이유는 사칙 덧셈 5을 기준으로 2+3까지만 값을 구하면 되기 때문입니다.
5 = 5 + 0
= 1 + 4
= 2 + 3
= 3 + 2
= 4 + 1
여기서 2+3뒤 부터 구해지는 값인 3+2와 4+1은 2+3과 1+4 값과 동일하기 때문에 굳이 구할 필요가 없습니다. (2+3과 3+2에서 달리지는 부분을 n1-n2와 n2-n1 방법 등으로 구했기 때문)
전체 코드는 깃허브에서 확인 가능합니다.
전체 코드는 깃허브에서 확인 가능합니다.
댓글
댓글 쓰기