[Programmers- LEVEL2] 124나라의 숫자, 기능 개발, 더맵게

123나라의 숫자

---

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

코딩테스트 연습 - 124 나라의 숫자

 

초반 코드

def solution(n):
    arr = ['1','2','4']
    dp = ['0','1','2','4','11', '12', '14', '21', '22', '24', '41', '42','44']
    len = 12
    k = 4
    if(n <= 12):
        return dp[n]
    else:
        while 1:
            if len >= n:
                return dp[n]
            for i in range(3):
                dp.append(dp[k]+arr[i])
                len = len+1
            k = k+1

정확도 테스트는 다 맞았지만, 효율성 테스트에서는 통과 하지 못했다. 아무래도 O(n)으로 하면 n이 500,000,000 일때 최소 5억번의 연산이 이루어져서 그런 것 같다. --> 모든 요소에 대해서 탐색하지 않아도 되는 방법을 찾아야한다.

 

dp를 쓰지 않고, 그냥 나눗셈만 이용해서 값을 한번에 나올 수 있는 방법을 생각해 냈다.

def solution(n):
    arr = ""
    while 1:
        if(n<1):
            break
        if n%3 == 0:
            arr = arr + '4'
        elif n%3 == 1:
            arr = arr + '1'
        else:
            arr = arr + '2'
        n = (n-1)//3
    return arr[::-1]

내 힌트 풀이는 다음과 같다. 

 

기능 개발

---

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

코딩테스트 연습 - 기능개발

import math
def solution(progresses, speeds):
    day = []
    for i in range(len(progresses)):
        day.append(math.ceil((100 - progresses[i])/speeds[i]))
    prev = day[0]
    cnt = 0
    answer = []
    for k in day:
        if prev < k:
            prev = k
            answer.append(cnt)
            cnt = 1
        else:
            cnt = cnt + 1
    answer.append(cnt)
    return answer

문제가 너무 직관적이라 다로 풀이는 안적는다.

 

 

더 맵게

---

https://programmers.co.kr/learn/courses/30/lessons/42626?language=python3 

코딩테스트 연습 - 더 맵게

import heapq

def solution(scoville, K):
    q = []
    for i in scoville:
        heapq.heappush(q, i)
    count = 0
    while q[0]<K:
        if len(q) == 1:
            return -1
        a = heapq.heappop(q)
        b = heapq.heappop(q)
        c = a+(b*2)
        count = count+1
        heapq.heappush(q,c)

    return count

이문제도 직관적으로 풀 수 있다.  python의 heapq라는 기능만 안다면 바로 풀 수 있는 문제이다.