[🥲 프로그래머스] N으로 표현 (Dynamic Programming)

https://programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현

 

🥺 내가 푼 풀이

# 내가 푼 풀이 44.4점 ㅜㅜ

# 리스트가 들어오면, 해당 리스트에 사칙연산을 해주는 함수
def DP(N, l):
    answer = []
    for i in l:
        answer.append(i+N)
        answer.append(i*N)
        answer.append(i-N)
        answer.append(i/N)
    return answer + l
    
def solution(N, number):
    l = []
    answer = 0
    for idx in range(1, 9): # 최대 8번까지 시행
        l.append(int(str(N)*idx)) # 5,55,555..
        if l.count(number) != 0: # 목표 숫자가 있으면 스탑하고 인덱스 출력
            answer = idx
            break
        l = DP(N, l) # 없으면 추가 사칙연산
    if answer == 0:
        answer = -1
    return answer

8번의 모든 경우의 수를 구해서 number가 있는 경우 인덱스 리턴...인데 반 넘게 틀림 ㅠㅠ 왜일까??????

 

😘 참고한 풀이

def solution(N, number):
    dp = [[]] # [5], [55,5*5,5+5,5-5,5//5]... 등의 값이 저장
    # dp[n]은 dp[n-1], dp[n-2].. 등로 이루어져 있다는 것을 참고
    for i in range(1, 9): # 8번까지 시행
        temp = []
        for j in range(1, i): # dp[i] == dp[i-j],d[j]
            for k in dp[j]: 
                for l in dp[i - j]: 
                    temp.append(k + l) # 더하기
                    if k - l >= 0: # 0보다 크면 빼기
                        temp.append(k - l)
                    temp.append(k * l) # 곱하기
                    if l != 0 and k != 0: # 둘 다 0이 아니면 나누기
                        temp.append(k // l)
        temp.append(int(str(N) * i)) # 55, 555 등 처리
        if number in temp:
            return i
        dp.append(list(set(temp)))

    return -1

+ 마지막에 set()으로 변환해서 넣길래 궁금해서 바꿔서 실행해봤다.

놀랍게도 리스트만으로는 400ms가 넘었는데 set으로 하니 0.대를 유지...!

 

---

List 자료형에서는 시간 복잡도 O(N)
Set과 Dict는 시간 복잡도 O(1)

---

그렇다고 한다..!!!!