[프로그래머스] 큰 수 만들기 (Python)

연두·2021년 2월 21일
0
post-thumbnail

프로그래머스 - 큰 수 만들기


🤔 제출(이 안되는) 코드

이틀째 고민중인데 그럴싸한 답이 나오지 않는다!! 나는 아직 바보다
더 붙잡고 있다가는 내 정신건강에 해로울 것 같아서 구글링을 해보았다.

구글링 해보니 스택을 사용해서 pop 어쩌구... 대충 훑어보고 다시 도전했다.

그래도 못했다. 어딜 내놔도 부끄러운 내 코드 ㅋㅋ


🙏 다른 사람의 풀이

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        # stack에 있는 값이 number의 가장 앞 숫자보다 작은 경우에
        while len(stack) > 0 and stack[-1] < num and k > 0:
            # k값을 1 감소시키고
            k -= 1
            # stack에 있는 값을 제거해준 뒤
            stack.pop()
        # 새로운 값을 삽입해줌
        stack.append(num)
    # for문이 끝난 후에도 제거 횟수를 다 사용하지 않았으면 남은 횟수만큼 리스트 뒷부분 잘라줌    
    if k != 0:
        stack = stack[:-k]
    return ''.join(stack)

그리디 알고리즘을 사용할 때에는 정당성을 따져봐야 한다고 배웠다.
여기서 if k != 0: stack=stac[:-k] 와 같은 코드를 사용할 수 있었던 이유는, 이미 for문을 돌면서 앞에서부터 큰 순서대로 채웠기 때문이다.

0개의 댓글