99클럽 코테 스터디 20일차 TIL + greedy

 

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

 

 

📌오늘의 학습 키워드

• 자꾸 그리디랑 완전 탐색을 착각하는 나자신... 그리디는 어려운 점이 어떤 방법이 그리디한지 알기 어려워서가 아닐까 싶다.

✨공부한 내용 본인의 언어로 정리하기

• 사실 너무 오래 걸려서 다른 분이 짜신 코드를 참고했다. 스택을 이용해 해결했다.

📚오늘의 회고

• 어떤 문제가 있었고, 나는 어떤 시도를 했는지
  • 처음에는 재귀로 모든 경우의 수를 탐색 한 다음 큰 수 를 찾으려고 했으나 시간 초과가 떴다.
• 어떻게 해결했는지
  • 사실 어떤 것이 큰 수를 만드는 그리디 방식인지 몰라 다른 분들의 코드를 찾아봤고 스택을 통해 해결하는 방법을 찾았다. 
  • O(n)의 시간 복잡도를 가지는 방법으로 한 숫자씩 돌아가면서 만약 스택 가장 위에 있는 수가 현재 숫자보다 작으면 다 빼버리는 방식이었다.

<참고한 선생님의 링크>

프로그래머스 - 42883: 큰 수 만들기 - 자바 풀이(10번 시간초과)

 

[🤓문제 해결 코드] - 파이썬

def solution(number, k):
    candidates = set()
    num_list = [n for n in number]
    num_stack = []

    # 몇 번을 제거할 지 정하기
    for num in num_list:
        while num_stack and k > 0 and num_stack[-1] < num:
            num_stack.pop()
            k -= 1
        else:
            num_stack.append(num)
    if k == 1:
        num_stack.pop()
    return ''.join(num_stack)