[알고리즘] 탐욕법(Greedy) 프로그래머스 2단계 - 큰 수 만들기

def solution(number, k):
    
    # 숫자로 비교하기 위해 int형으로 바꾸고 list로 만든다.
    number = list(map(int, number))
    stack = []
    count = 0
    
    # stack 배열을 만들어 count가 k 값이 될때 까지 반복해준다.
    for n in range(len(number)):
        if count == k:
            break
        # stack이 비어있을 땐 number[n] 값을 넣는다.
        if len(stack) == 0:
            stack.append(number[n])
        # stack이 비어있지 않을 경우, 분기를 나눈다.
        else:
            while True:
                # 반복문을 도는 동안 stack의 길이가 0이 될 수도 있다.
                if len(stack) == 0:
                    stack.append(number[n])
                    break
                else:
                    # 들어갈 숫자가 stack[-1] 보다 크면 stack[-1]을 제거한다.
                    if stack[-1] < number[n]:
                        stack.pop()
                        count += 1
                        # count == k가 되면 반복문을 빠져나온다.
                        if count == k:
                            stack.append(number[n])
                            break
                    # 들어갈 숫자가 stack[-1] 보다 작거나 같으면 그대로 넣어준다.
                    else:
                        stack.append(number[n])
                        break
    
    # count와 k가 다른 경우 ex) number = "91111" / k = 2
    if count != k:
        number = number[:-k]
        stack = list(map(str, number))
        result = ''.join(stack)
        return result
    
    # count와 k가 같은 경우
    num = len(number) - k
    need = num - len(stack)
    
    # 필요한 자리수 만큼 number에서 가져온다.
    new_stack = []
    if need != 0:
        new_stack = list(number[-need:])
    
    # stack에 이어붙인다.
    stack.extend(new_stack)
    
    # 숫자로 바꿨던 원소를 string으로 바꾼 후 join한다.
    stack = list(map(str, stack))
    result = ''.join(stack)
    
    return result

풀이과정

1. 문자열 number을 int형으로 바꾼 후 배열에 넣는다.

2. stack 배열을 만들어 count가 k값이 될 때까지 반복한다.

• stack이 비어있을 땐 number[n] 값을 넣는다.
• 들어갈 number[n]이 stack[-1]보다 크면 stack[-1]을 제거한다.
• while문을 반복하면서 count와 k값이 같아지면 빠져나온다.

3. count와 k값이 다른 상태로 반복문을 빠져나올 수도 있다.

• ex) number = '91111' / k = 2

4. count와 k값이 같은 경우, 필요한 자릿수 만큼 number에서 가져온다.

• 가져온 값을 stack 배열과 합친다.
• int형으로 바꿨던 원소를 string으로 되돌린 후, join한다.

코드정리

• 각 자리 숫자를 비교하는 것이기 때문에 int형으로 바꿀 필요 없다.
• count를 만들지 않고 k 자체를 사용하면 된다.
• if count == k, if len(stack) == 0, if stack[-1] < number[n]을 하나로 합친다.

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