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

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

내 풀이

def solution(number, k):
    stack = []
    delete_count = k
    for char in number:
        while delete_count and stack and int(stack[-1]) < int(char):
            stack.pop()
            delete_count -= 1
        stack.append(char)

    return ''.join(stack[:-delete_count]) if delete_count else ''.join(stack)

처음에는 감을 못잡고 있다가, 질문게시판에서 스택을 이용하면 된다는 힌트를 보고 풀었다. 그리디에는 정해진 것이 없다. 그리디안에서 다른 자료구조와 알고리즘을 쓸 수도 있다.

print(solution("1924", 2), "94")
print(solution("1231234", 3), "3234")
print(solution("4177252841", 4), "775841")
print(solution("99991", 3), "99")
print(solution("111119", 3), "119")
print(solution("7777777", 2), "77777")
print(solution("10000", 2), "100")
print(solution("87654321", 3), "87654")
print(solution("01010", 3), "11")

사용한 반례들이다. 처음에는 ("7777777", 2) 같은 경우를 고려하지 않아서 테스트케이스 12번에서 에러가 났고, 나중에는 ("01010", 3) 과 같은 경우를 고려하지 않아서 11번에서 에러가 났다. 만약 지울 수 있는 횟수 k를 다 사용하지 않았으면 마지막에서 그만큼 뒤에서 잘라서 반환해야한다.