[알고리즘] 프로그래머스_큰 수 만들기

권윤경·2021년 10월 1일
0

알고리즘

목록 보기
7/13
post-thumbnail

큰 수 만들기

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

문제설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한조건

number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.

내 코드

githubGist URL

def solution(number, k):
    answer = []
    
    for i in number:
        while k > 0 and answer and answer[-1]<i:
            answer.pop()
            k -= 1
            print(answer)
        answer.append(i)
        print(answer)
    return ''.join(answer[:len(answer) - k])

문제를 이해하기까지 오랜 시간이 걸렸다. 단순 큰 수를 만드는게 아닌 탐욕적 알고리즘을 활용하여 풀어야하는것을 알지 못했기 때문이다.

탐욕적 알고리즘이란 현재 상황에서 가장 좋아 보이는 것을 선택하는 알고리즘이다.
탐욕적 알고리즘은 매순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다는 특징을 가지고 있다. 또한 매 순간의 선택이 최적의 선택이었을지라도 결론적으로 최적이 아닐 수 있다.
❗️따라서 탐욕적 알고리즘을 이용하여 문제를 해결할 경우에는 해당 해법이 정당한지에 대해서 반드시 확인해 보아야한다.

문제는 stack을 활용하여 풀었다. stack에 마지막으로 입력된 값을 다음에 올 값과 비교하여 다음에 오는 값이 클때 스택에 저장된 제일 마지막 값을 삭제하는 것을 반복문을 통해 연산하였다. 마지막 return값은 문자열로 반환해야 했기때문에 stack에 저장된 값을 join함수를 사용하여 반환하였다.

0개의 댓글