N으로 표현 문제
프로그래머스 링크
https://programmers.co.kr/learn/courses/30/lessons/42895
풀이
def solution(N, number)
코드
def solution(N, number):
#재귀 알고리즘으로 풀어보기
answer = RecursiveSol(N, number, 0, 0)
#최솟값이 8보다크면 -1을 리턴해야 하지만 min함수를 쓰기위해 9로 넣을것이다.
if answer > 8:
answer = -1
return answer리뷰
프로그래머스의 main함수와 같은 solution함수이다.
인자로
N : 1~9 사이의 정수
number : N과 사칙연산을 이용해 만들어야할 정수가 들어온다.
재귀 알고리즘을 사용하기 위해 코드가 분산되어 내용이 짧다.
def RecursiveSol(N, number, level, nums)
코드
def RecursiveSol(N, number, level, nums):
#재귀 탈출조건 1, N을 사용하여 number를 완성했을 때 level == N사용개수 반환
if(nums == number):
return level
#제약조건상 N의 최대 사용개수는 8개, 8개까지 사용했을 때 정답이 나오지 않았다면 9반환
elif(level >= 8):
return 9
result = []
dup_N = makeDup(N, 8-level) #N, NN, NNN.....
#dup_N에서 만든 N반복 숫자들 각각 사칙연산을 적용하여 재귀적용
for idx in range(len(dup_N)):
result.append(RecursiveSol(N, number, level + idx + 1, dup_N[idx] + nums))
if(nums != 0 ):
result.append(RecursiveSol(N, number, level + idx + 1, abs(dup_N[idx] - nums)))
result.append(RecursiveSol(N, number, level + idx + 1, dup_N[idx] * nums))
result.append(RecursiveSol(N, number, level + idx + 1, nums//dup_N[idx]))
#최솟값만 리턴한다.
return min(result)리뷰
먼저, 인자로 들어오는 정보들은 아래와 같다.
N : solution에서 받은 1~9 사이의 정수
number : solution에서 받은 number
level : 현재까지 사용된 N의 개수
nums : 사칙연산으로 만들어진 정수
이후,
if(nums == number):
return level
elif(level >= 8):
return 9에서 재귀 알고리즘의 탈출조건을 만들어 준다.
만약 문제에서 제시된 number와 함수에서 사칙연산으로 만들어진 nums가 같다면 현재의 level 반환.
또한, 제약조건인 N의 최대 사용개수 8개를 모두 썼는데, 목표한 number가 안됬다면 9반환,
여기서 9를 반환하는 이유는, 사칙연산에서 나온 4가지의 결과중 가장 최소값을 구하기위해 min()을 사용하기 때문이다.
만약 문제에서 원하는 조건인 -1을 그대로 반환한다면 제대로 계산된 결과가 아닌 -1이 결과로 나오기 때문에 최대 사용개수인 8개를 넘는 9개로 반환해준다.
result = []
dup_N = makeDup(N, 8-level) #N, NN, NNN.....makeDup(N, 8-level) 함수는 아래 설명할 것이지만 간단하게 예를들면,
5를 [5, 55, 555, 5555, 55555, 555555, 5555555] 이렇게 만들어, 그 리스트를 반환해주는 함수이다.
level은 현재까지 사용된 N의 개수이며, 8은 사용할 수 있는 N의 최대 개수이기 때문에
8 - level은 앞으로 사용할 수 있는 N의 개수가 된다.
for idx in range(len(dup_N)):
result.append(RecursiveSol(N, number, level + idx + 1, dup_N[idx] + nums))
if(nums != 0 ):
result.append(RecursiveSol(N, number, level + idx + 1, abs(dup_N[idx] - nums)))
result.append(RecursiveSol(N, number, level + idx + 1, dup_N[idx] * nums))
result.append(RecursiveSol(N, number, level + idx + 1, nums//dup_N[idx]))
#최솟값만 리턴한다.
return min(result)위 makeDup에서 만들어진 리스트를 하나씩 사용해 사칙연산 및 재귀로 들어가는 반복문이다.
처음 재귀를 시작할 때, nums가 0이기 때문에 사칙연산의 결과가 0또는 N으로만 나오게 된다.
따라서 조건문으로 nums == 0일때는 "+"연산만 진행하게 하여 중복연산을 피한다.
탈출 조건으로 number가 맞게 나왔다면 현재 사용된 N의 개수 "level"이 반환되고,
number가 아니라 N의 최대개수를 넘겨 탈출됬다면, 9가 반환될 것이다.
이 반환값들을 result 리스트에 넣어서 그 중 최솟값만 반환한다.
재귀 안쪽에서 최솟값들을 모아서 그중 최소값만 뽑아 결국 가장 최소값만 solution함수로 반환될 것이다.
def makeDup(N, left)
코드
def makeDup(N, left): #N, NN, NNN, NNN....이렇게 리스트로 반환해주는 함수
return [int(str(N)*i) for i in range(1, left+1)]리뷰
인자로써 N과 현재 사용할 수 있는 N의 개수가 들어온다.
int형인 N을 str로 바꿔 i만큼 곱해준다.
만약 makeDup(9, 3)으로 들어왔다면
9를 문자열인 "9"로 바꾸고 for 반복문에서 1~3+1까지 반복하여
"9", "99", "999"로 만들어주고, 이를 다시 int형으로 만들어 [9, 99, 999]인 리스트로 반환해준다.
더 나은 방법
def solution(N, number):
# 1~8번까지 N을 사용해서 만들 수 있는 수의 집합
# s[i] 에는 N을 i+1개를 사용해서 만들 수 있는 수의 집합이 들어간다.
s = [set() for x in range(8)]
#N ~ NNNNNNNN 이 숫자들을 미리 담아놓는다.
for i,x in enumerate(s, start=1):
x.add(int(str(N) * i))
# N을 1번에서 8번까지
for i in range(len(s)):
# i-j 해서 남은 N의 개수?
for j in range(i):
#op1 은 0 ~ i-1까지, op2는 i-1 ~ 0까지 해서 모든 경우의수를 입력한다.
for frontnum in s[j]:
for tailnum in s[i - j - 1]:
s[i].add(frontnum + tailnum)
s[i].add(frontnum - tailnum)
s[i].add(frontnum * tailnum)
if(tailnum != 0):
s[i].add(frontnum // tailnum)
#N을 1~8개까지 민들어 set으로 저장한 후,
#그 number가 s[i] 존재한다면 answer = i+1을 넣는다.
if number in s[i]:
answer = i + 1
break
# 아니라면 기본값이 -1이 반환된다.
return answer