[프로그래머스][Greedy] : 큰 수 만들기 - Python

🔴 Greedy 알고리즘

• 현재 상황에서 가장 좋은 방향을 선택하는 방법
• 탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

 

🟠 문제

 

🟡 접근 방법

1. stack 생성 > python에서는 list 활용 가능
2. 핵심은 스택의 마지막 값이 push 할 값보다 작다면 크거나 같은 값이 나올 때까지 값들에 대해서 pop을 하는 것이다.
3. pop을 할 때마다 k를 감소시켜주고, k가 0이 되면 더 이상 삭제할 수 없으므로 남은 수를 모두 넣어준다.
4. 수를 다 비교 했는데 k가 남아있다면, k의 값만큼 뒤에서부터 잘라준다
5. 이렇게 하면 O(n)의 시간 복잡도로 문제를 해결할 수 있다.

🟢 나름의 해설

1. stack 리스트 활용 가능
2. stack의 마지막 값이 push 할 값보다 작다면 크거나 같은 값이 나올 때까지 값들에 대해서 pop 한다.
3. number 을 돌려 조건문을 만족할 경우 명령문 반복

여기서 조건문은 3개

1. k > 0

2. stack이 비어있지 않다

3. stack의 마지막 값 < num

 

stack을 pop

k--

stack에 num을 push (append 활용)

 

k > 0 이상이면 스택에서 k개 삭제 후 join해서 결과 값 반환