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

그리디 알고리즘을 활용해야 하는 문제 였습니다ㅇㅅㅇ!

---

<문제 설명>

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

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

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

제한 조건

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

<입출력 예>

number	k	return
1924	2	94
1231234	3	3234
4177252841	4	775841

---

내가 생각한 풀이

순서가 흐트러지지 않고, 입력된 수에서 k개의 수가 제거됐을때 만들 수 있는 가장 큰 숫자를 구해야 함

입력 문자열의 숫자를 한개씩 순서대로 방문하며 result 스택에 추가함

만약 가장 최근 result에  담겨진 숫자보다 현재 방문한 숫자가 더 크고 k만큼 모두 제거 된 상태가 아니라면

result를 pop()시키고 입력 값 중 1개를 제거한 것이기 때문에 k를 -1 시킴

 

모든 방문을 끝마친 후(입력값을 조건 비교 과정을 걸치며 result에 추가한 후) k>0이라면,

k만큼 result를 pop()시킴 (가장 마지막에 추가된 값들 부터 제거)

 

결과값을 문자열 형태로 반환해줘야 하기 때문에 join함수를 이용해 리스트를 문자열로 변경해 반환

 

코드

def solution(number, k):
    result = []
    for n in number:
        while result and result[-1] < n and k > 0:
            result.pop()
            k -= 1
        result.append(n)
    while k > 0:
        result.pop()
        k-=1
    return "".join(result)

4번째 라인의 while result and result[-1]<n and k>0: 에서

result 조건을 넣은 이유는 result가 비어있지 않을때만 동작하게 하려고 넣은 것

result가 비어 있는 상태에서 while문이 동작하게 되면,

비교할 값이 없으며 result[-1] 조건에 대해 인덱스 오류가 발생함!

 

문제출처: https://programmers.co.kr/learn/courses/30/lessons/42883

코딩테스트 연습 - 큰 수 만들기 | 프로그래머스