bright

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        while len(stack) > 0 and stack[-1] < num and k > 0:
            k -= 1
            stack.pop()
        stack.append(num)
    if k != 0:
        stack = stack[:-k]
    return ''.join(stack)

1. 분류 : 스택 / 큐 

2. 풀이 방법 

큰 수를 앞 쪽에 배치하는 문제이다. 가장 큰 수가 나올 때 까지 스택에 넣고 빼고를 반복한다. 

programmers.co.kr/learn/courses/30/lessons/42883

def solution(n):
    answer = 0
    
    dp = [0]* ( n+1 ) 
    dp[1] = 1 
    dp[2] = 2 
    
    if n < 3 : 
        answer = dp[n]
    else: 
        for i in range(3,n+1):
            dp[i] = ( dp[i-1]+ dp[i-2]  ) % 1000000007 
        answer = dp[n]  
    
    return answer

1. 분류 : 다이나믹 프로그래밍 

2. 풀이 : 

가장 기초적인 다이나믹 프로그래밍 문제이므로 잘 이해하고 넘어간다. 

왼쪽 부터 i-1 까지의 길이가 덮여 있으면, 2x1 을 채우는 경우의 수는 1가지 밖에 없다. 

왼쪽 부터 i-2 까지의 길이가 덮여 있으면 2x2 를 채우는 경우의 수는 2가지이지만, 모두 세로인 경우는 위의 방식에서도 count 되므로 가로로 채우는 경우의 수 1가지 라고 할 수 있다. 

따라서 점화식은 An = An-2 + An-1 이 된다. 

3. 유의사항 :

수가 아주 커질 수 있으므로  % 1000000007  처리를 어디서 하느냐에 따라서 효율성 문제가 걸릴 수 있다. 

나누기 연산한 값은 항상 동일하므로 dp 리스트 안에 넣는 과정에서 나눠 주자 

( answer 에 넣을 때 나누거나 return 할 때 나누면 효율성부분 점수 받기가 어렵다 ) 

def solution(n):
    answer = ''
    
    max_num = 3  # 해당 자리수에서 가장 큰 수, 즉 4444.... 
    cnt = 1 
    
    while n > max_num :
        cnt += 1 
        max_num += 3**cnt

    while n > 0 :
        if n > max_num - (max_num - max_num//3 +1 )//3 : 
            answer += '4'
            n -= 3**(cnt)
        elif n > max_num - ((max_num - max_num//3 +1)//3)*2 : 
            answer += '2'
            n -= 2*3**(cnt-1)
        else : 
            answer += '1'
            n -= 3**(cnt-1)

        max_num -= 3**cnt
        cnt -= 1 
    return answer

1. 분류 : 구현..?  

2. 풀이 방법 : 

1 자리 수 : 1 2 4 

2 자리 수 : 11 12 14 / 21 22 24 / 41 42 44 

3 자리 수 : 111 112 114 121 122 124 141 142 144 / ...  444 

n 자리 수의 갯수 : 3^n 

각 자리 수 별 가장 큰 수 ( 4로만 이루어진 수 ) : 3 + 3^2 + 3^3 .. 

step 1 )  내가 몇 자리 수 인지 인지하고 내 자리수에서 가장 큰 값을 찾는다. 

step 2 )  각 자리수의 숫자는 3 단위로 이루어 진다.  

            예를 들어, 2 자리 수인 경우에 상위 1/3 는 맨 앞자리가 4,  2/3 은 2, 마지막은 1 이다. 

            따라서, 자리별로 적절하게 빼 가면서 어떤 수가 올지 파악한다.