[프로그래머스][DP] N으로표현 python (200920)

1. 문제설명 

 

 

 

 

여기서 핵심은 이거다 

N 이 5라고 했을 때 N의 사용횟수마다 나오는 숫자들을 구해보자면,

 

1번 사용 : 5

2번 사용 : 5 + 5 , 5 - 5, 5 * 5, 5 / 5, 55

3번 사용 : 1번 사용과 2번 사용의 조합으로 구해진다***    

 

1) 1번 사용 (+-/*) 2번 사용  -->  총 생성 갯수 : 1 (1번 사용 갯수) *  5 (2번 사용갯수)  = 5 개 숫자 생성

5  + 5 + 5 ,

5  -  5 + 5 ,

5  *  5 + 5 ,

5  /  5 + 5 ,

5 55

 

2) 2번 사용 (+-/*) 1번 사용  --> 총 생성 갯수 : 5 (2번 사용갯수) * 1 (1번 사용 갯수) = 5 개 숫자 생성

5 + 5  + 5  + ,  

5 + 5 - 5  , 

5 + 5  * 5   ,

5 + 5 / 5  ,  

55  5

 

3번 사용 : 5 + 5  + 5  + ,  5 + 5 - 5  , 5 + 5  * 5   ,5 + 5 / 5  ,  555,  5  + 5 + 5 ,5  -  5 + 5 ,5  *  5 + 5 ,5  /  5 + 5 , 555 

 

 

4번 사용 : 

1) 1번 사용 (+-/*) 3번사용 

2) 2번 사용 (+-/*) 2번 사용

3) 3번 사용 (+-/*) 1번 사용  

 

따라서 M번 사용했다고 하면 

1) 1번 사용 (+-/*) M-1 번 사용  --> 총 생성 갯수 : 1 (1번 사용 갯수)  *   ? ( M-1 번 사용 갯수)  = ?? 개 생성

2)

...

m-1) M-1 번 사용 (+-/*)  1번 사용 --->  총 생성 갯수 : ? ( M-1 번 사용 갯수) * 1 (1번 사용 갯수) = ?? 개 생성 이런식이 된다.

 

 

따라서 코드를 짤때 우리는 , 

전체 사용 횟수 증가해주면서  --> for 

해당 사용 횟수에서 나올 수 있는 두개의 조합 구하고  ---> for 

두 개의 조합에서 나올 수 있는 모든 수 구하고 --> for for 

 

총 4중 for 문이 불가피한 상황이다... 

대신 여기서는 전체 사용 횟수를 8로 제한해뒀고, number가 등장하는 순간 바로 return 을 때리면, 런타임 에러는 안걸린다. 

 

 

 

2. 풀이 

 

1) 리스트로 접근했을 때 지옥의 런타임에러 

def calN(num1, num2, number):

    all_num_list = []

    for num1_num in num1:
        for num2_num in num2:

            all_num_list.append(num1_num + num2_num)
            all_num_list.append(num1_num - num2_num)
            all_num_list.append(num1_num * num2_num)
            if num2_num != 0:
                all_num_list.append(int(num1_num / num2_num))
            if number in all_num_list:
                return "Find"  # 만약 중간에 number 나오면 바로 false
    return all_num_list

def solution(N, number):
    num_dict = {1:[N,0]}
    result = False

    for idx in range(2,9): # dict idx
        print(idx)
        now_num_list = []

        if number == int(str(N)*idx):
            return idx

        for key in range(1,idx): # 수의 조합 4 => 1,3 /  2,2, / 3,1
            key_list = calN(num_dict[key],num_dict[idx-key],number) # 1번 2
            key_list.append(int(str(N)*idx))
            if key_list == "Find":
                return idx
            else:
                now_num_list.extend(key_list)
        num_dict[idx] = now_num_list

    if not result:
        return -1

 

구조는 위에서 말한 풀이와 같다. 

 

따라서 코드를 짤때 우리는 , 

전체 사용 횟수 증가해주면서  --> for 

해당 사용 횟수에서 나올 수 있는 두개의 조합 구하고  ---> for    ==> solution 함수 

두 개의 조합에서 나올 수 있는 모든 수 구하고 --> for for   ==> calN 함수

 

 

해당 풀이법에서는 딕셔너리에 각 사용 횟수때마다 생성되는 수를 리스트로 담아두려했다. 

now_num_list 에 idx 만큼 사용했을 때 만들어지는 수가 모두 담기고 

각 조합별로 생성되는건 now_num_list 를 extend 해서 담기도록 했는데...

 

 

 

두번째 예시 에서 런타임 에러다 :( 

값 〉	5,
기댓값 〉	31168
실행 결과 〉	-1

이 예시는 8개의 숫자조합을 다 구하고도 답이 나오지 않아 -1 이 나오는 상황인데 

8까지 다 도는 와중에 런타임이 뜬거다 

 

이유 1 :  list extend 의 time complexity 는 o(len(...)) 이다. 길이만큼 걸리는 것 

          비록 숫자 조합이 8까지 밖에 안되지만 8 안에 속하는 경우의수는 엄청 많기때문에 

          이걸 담고 다시 extend 하는 과정에서 런타임이 걸린듯.  (실제로 프린트 찍어서 돌려보면 5에서 막힌다.) 

 

이유 2 : 중복되는 숫자들도 다 담기는 것 ***

        중복 숫자들이 담겨서 리스트 길이가 무지막지하게 길어지는 듯하다.

        여기서는 중복제거해주고 딱 numbers 랑 같은 숫자만 찾아주면 되니까 set으로 해보겠다. 

 

 

 

따라서 리스트가 아닌 셋에 담는 식으로 진행을 해보겠음 . ! 

 

from collections import defaultdict


def findcollabnum(num1_set, num2_set, number):

    total_num_set = set()
    for num1 in num1_set:
        for num2 in num2_set:
            total_num_set.add(num1 + num2)
            total_num_set.add(num1 - num2)
            total_num_set.add(num1 * num2)
            if num2 != 0 :
                total_num_set.add(int(num1 / num2))

            if number in total_num_set:
                return "FIND"

    return total_num_set



def solution(N,number):
    dp = defaultdict(set)

    trigger = False

    for idx in range(1,9):
        if number == int(str(N)*idx):
            return idx
        else:
            dp[idx].add(int(str(N) * idx))  # 연속 숫자 경우도 추가해주기
            for m_idx in range(1,idx):
                result = findcollabnum(dp[m_idx], dp[idx-m_idx], number)
                if result == "FIND":
                    return idx
                else:
                    # print(result)
                    dp[idx] |= result

    if not trigger:
        return -1

 

두가지 고오급 스킬을 써보았다. 

 

1) defalutdict(set) 으로 값들이 빈 set으로 되도록 만들었다. 

2) dp[idx] |= result 를 사용했는데 

이건 리스트의 concat과 같은 역할을 set에서 하는 거다.

dp[idx] 안에 있는 set 값 유지하면서 result 안의 set 값들 concat 시키는  

리스트는 += 로 가능한데, 셋은 |= 을 써야한다. 

 

+= 의 time complexity O(N)

|= 의 time complexity O(len(s)+len(t))

+)  자료형 별 concat 

l1 = [3]
l2 = [2,3,1,4]
l1 += l2
# l1 |= l2    #### ERROR ! 
print(l1)
>>> [3, 2, 3, 1, 4]

s1 = {3}
s2 = {2,3,1,4}
# s1 += s2    #### ERROR ! 
s1 |= s2
print(s1)

>> {1, 2, 3, 4} (중복제거) 

 

 

 

 

3. 정리 

- 중복 제거 해줘도 되는 경우는 무조건 set 써서 자료형 줄이기

- 이중 포문에서 더 들어갈 경우 함수 만들기 (뭐 만든다고 연산 속도가 달라지지는 않지만, 보기에 깔끔함)

- 반복문 깊어지면 트리거 만들어서 정답문 만들어서 리턴하도록

- defalutset , |= 두개 다음에 꼭 사용해보기 

 

 

 

 

*** defalutset 참고자료 

 

dongdongfather.tistory.com/69

[파이썬 기초] 유사 딕셔너리 defaultdict() 활용법

|= 연산자 설명 자료 

 

python-reference.readthedocs.io/en/latest/docs/sets/op_update.html

|= (update) — Python Reference (The Right Way) 0.1 documentation