[프로그래머스][그리디]큰 수 만들기

문제

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

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

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

제한 조건

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

입출력 예

numberkreturn

1924	2	94
1231234	3	3234
4177252841	4	775841

 

처음에 각 인덱스를 빼서 모두 비교했는데 시간초과가 났다.

시간초과 난 풀이

고민하다가 검색을 해보니 스택을 이용하면 된다는 사실을 알았다..!
일단 넣고 더 큰게 오면 기존에 있던걸 뺄지 말지 결정하는 것이다.

def solution(number, k):
    answer = ''
    if min(number)==max(number):
        return number[:-k]
    answer+=number[0]
    for i in range(1,len(number)):
        while len(answer)>0 and answer[-1]<number[i] and k!=0:
            k-=1
            answer=answer[:-1]
        answer+=number[i]
        if k==0 and i<len(number)-1:
            answer+=number[i+1:]
            break
    while(k>0):
        idx=answer.index(min(answer))
        answer=answer[:idx]+ answer[idx+1:]
        k-=1
    return answer

1. 처음에 모든 수가 같으면 (ex 111111,99999) 뒤에서 k개를 빼고 바로 반환한다.
2. answer에 일단 index0 을 삽입
3. 그 다음 index가 더 큰게 나오면 이전에 있던것들중에서 뺀다. (단 k개보다 많이 빼면안됨)

4. k개만큼 뺀 이후에 뒤에 남아있으면 붙여준다.
5. k개만큼도 못 뺐을 경우에는 작은 값을 지워줬다.

 

 

다른사람 풀이 )

1. 어차피 number를 순회하면서 다 넣으니까 k 개만큼 뺸 이후에 뒤에 남아있는것들도 다 붙이게 된다. 따라서 내가 쓴 for문안의 if 문은 굳이 쓸 필요 없었다.
2. k 개만큼 못 뺐다는것은 그 뒤에 계속 작은 숫자들만 나왔다는 것이다. (ex 54321) 따라서 뒤에서부터 남은 k개만큼 지워주면된다.