[파이썬] N으로 표현

문제 설명

 

아래와 같이 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번만 사용하여 표현할 수 있습니다.

출처

※ 공지 - 2020년 9월 3일 테스트케이스가 추가되었습니다.

 

 

🎀 나의 풀이

 

def solution(N, number):
    answer = [set([int(str(N)*i)]) for i in range(1, 9)]   # N을 각 인덱스별로 인덱스+1번 반복
    
    if N == number :
        return 1

    for i in range(1, 8) :      # 1에서 7까지
        for j in range(i) :
            for y in answer[j]:
                for x in answer[i-j-1] :    
                        answer[i].add(y+x)
                        answer[i].add(y*x)
                        answer[i].add(y-x)
                        if y > 0 :		# 0으로 수를 나누지 못하게
                            answer[i].add(x//y)
                if number in answer[i] :	# 찾으면
                    return i+1			# 인덱스가 0부터 시작이니까

    return -1			# 최솟값이 8보다 큼

 

제출하니 테스트 9번만 틀려서 N==number일 때 바로 1을 리턴해주니 통과 ㅎㅎ

set(int(str(N)*i))를 하니 iterable이 아니라고 error 떴었음.

iterable은 반복 가능한 객체다. list, dict, set, str, bytes, tuple, range가 iterable이다.

answer[8]은 초기에 넣은 값 자체가 8번이라서 반복문 범위에 넣으면 안 됨.

 

 

 

🍖 다른사람 풀이

 

# 출처 : https://gurumee92.tistory.com/164
def solution(N, number) :
  answer=0  
  if N == number :
    return 1

  # 1. [SET*8] 초기화
  s=[set() for x in range(8)]

  # 2. 각 set마다 기본 수 "N"*i 수 초기화
  for i, x in enumerate(s, start=1) :
    x.add(int(str(N)*i))    

  for i in range(1, 8) :
    for j in range(i) :
      for op1 in s[j]:
        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

 

n번 set은

1. 숫자 N을 n번 사용한 것과

2. 이전 n번 set집합들을 사칙연산 한 집합이다.

예를 들어 N이 2일 때, 3번 set은 

333과

1번 set과 2번 set을 사칙연산한 집합

2번 set과 1번 set을 사칙연산한 집합으로 이루어짐.

-, / 때문에 위와 같이 (1번, 2번), (2번, 1번)으로도 계산하는 것.

 

def solution(N, number):
    lst = [set() for _ in range(9)]		# 인덱스 1부터 사용
    lst[0].add(0)
    lst[1].add(N)
    if N == number:
        return 1

    for i in range(2, 9):
        ni = int(str(N) * i)
        if ni == number:
            return i
        lst[i].add(ni)

        for j in range(1, i):
            for n in lst[j]:
                for m in lst[i - j]:
                    if n + m == number:
                        return i
                    lst[i].add(n + m)
                    if n - m == number:
                        return i
                    lst[i].add(n - m)
                    if n * m == number:
                        return i
                    lst[i].add(n * m)
                    if m != 0:
                        if n // m == number:
                            return i
                        lst[i].add(n // m)

    return -1

 

계산할 때마다 number랑 같은지 확인한다.

 

def solution(N, number):
    S=[0, {N}]			# 메모이제이션

    for i in range(2, 9):   # N을 사용하는 횟수가 8보다 크면 -1리턴이니까 8까지
        case_set={int(str(N)*i)}
        for i_half in range(1, i//2+1):
            for x in S[i_half]:
                for y in S[i-i_half]:		# 사칙연산
                    case_set.add(x+y)
                    case_set.add(x-y)
                    case_set.add(y-x)
                    case_set.add(x*y)
                    if x != 0:			# 0으로 나누면 에러뜨니까
                        case_set.add(y//x)
                    if y != 0:
                        case_set.add(x//y)
        if number in case_set:
            return i
        S.append(case_set)
    return -1

 

첫번째 for문은 N을 2부터 8까지 연속해서 만든다.
두번째 for문은 1부터 i의 절반까지 반복한다. 
세번째 for문은 리스트 S에서 값을 꺼낸다.
S에서 인덱스1부터 끝가지 사칙연산을 한다(모든 경우의 수).
네번째 for문도 리스트 S에서 값을 꺼내는데 인덱스1부터 시작하게 됨.
모든 사칙연산을 계산해서 case_set에 넣는다. set은 중복제거해서 좋음.

 

 

 

 

문제 출처 : 프로그래머스