[프로그래머스] 큰 수 만들기 - 파이썬(pytyon)

 

나의 풀이

def solution(number, k):
    length = len(number) - k
    answer = ""
    i = 0
    index = length #가장 높은 자리
    
    while len(answer) != length :
        if index == 0 : break
        max_index = i
        for x in range(i, len(number)-index+1) :
            if number[x] == '9' : 
                max_index = x
                break
            elif number[x] > number[max_index] : max_index = x
            
        answer += str(number[max_index])
        i = max_index+1
        index -= 1
    
    return answer

으아... 구현 아이디어를 떠올리는데 시간이 많이 걸렸던 문제ㅠㅠ

내가 생각한 방법은 다음과 같다.

 

우리는 k개를 제거한 len(number)-k 자리수를 만들어야 한다.

따라서 가장 높은 자리부터 낮은자리까지 각 자리수에 올 숫자를 확정시켜야 한다.

 

"4177252841", k=4 가 주어졌을 때 우리는 6자리수 를 만들어야 한다.

따라서 가장높은 자리숫자부터 확정시켜야 한다. _ _ _ _ _ _

이때, 해당 숫자의 뒤에 있는 숫자개수가 5개이상이여야지만, 첫번째 숫자가 될 수 있다.

 

즉, 주어진 number 에서 8은 가장 큰 숫자이지만, 뒤에 남아있는 숫자가 41 밖에 없으므로 첫번째자리 에 올 수 없다.

이를 구현한 코드가 for x in range(i, len(number)-index+1) : 이다.

i 는 이전까지 구한 자리숫자(즉, 확정된 숫자) 다음 숫자이다.

 

그리고, 숫자가 9일 경우 뒤에 있는 숫자들을 탐색하지 않아도, 해당 숫자가 가장 큰 숫자이므로 빨리 탐색을 끝낼 수 있다.

이 코드를 추가하지 않아, 처음에는 하나의 테스트케이스에서 시간 초과가 발생하였다.

 

1. 4177252841 에서 첫번째자리수를 구하기 위해 i=0~4(10-index 6) 까지 for문을 돌며 확인한다. 이때 첫째자리는 7로 확정된다. index변수의 경우, 첫째자리가 6, 둘째자리가 5, ... 마지막 자리가 1이 된다.

-> 7 _ _ _ _ _

2. 이제 7의 다음숫자부터 탐색하므로 i=3 이 된다. (7의 인덱스는 2) 

둘째 자리수를 구하기 위해 i=3~5(10-index 5) 까지 확인하는데 , 이때 둘째자리도 7로 확정된다.

-> 7 7 _ _ _ _

3. 7의 인덱스 3 다음부터 탐색하므로 i=4 가 된다.

셋째 자리수를 구하기 위해 i=4~6(10-index 4) 까지 확인하는데, 셋째자리는 2 5 2 중 가장 큰 5로 확정된다.

-> 7 7 5 _ _ _ 

4. 5의 인덱스 5 다음부터 탐색하므로 i=6 가 된다.

넷째 자리수를 구하기 위해 i=6~7(10-index 3) 을 확인하는데, 넷째자리는 2 8 중 큰 8로 확정된다.

-> 7 7 5 8 _ _ 

5. 8의 인덱스 7 다음부터 탐색하므로 i=8 이 된다.

다섯째 자리수를 구하기 위해 i=8~8 을 확인하므로, 다섯째자리는 4가 된다.

-> 7 7 5 8 4 _

6. 마지막으로 i=9가되고, for문을 돌지 않고 바로 answer 에 i번째 숫자가 추가된다.

-> 7 7 5 8 4 1

 

 

다른 풀이

stack 을 이용한 풀이... 이 문제에 stack 을 사용할 생각조차 안했는데,, 냅다 문제를 구현하기 보다 조금 더 생각하는 힘을 길러야겠다... ㅠㅠ

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

제거해야할 숫자 (k) 가 남아있을 때까지,

stack의 top 에 있는 숫자와 현재 숫자를 비교하여 내가 더 크다면 stack의 top에 있는 것을 pop하는 원리이다.