99클럽 코테 스터디 20일차 TIL + 탐욕법(Greedy)

오늘의 문제 - 탐욕법(Greedy)

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

https://school.programmers.co.kr/learn/courses/30/lessons/42883

---

내 풀이 및 접근 방식

스택 사용 풀이

def solution(number, k):
    answer = [] # Stack
    
    for num in number:
        while k > 0 and answer and answer[-1] < num:
            answer.pop()
            k -= 1
        answer.append(num)
        
    return ''.join(answer[:len(number) - k])

 

풀이

1. 반복문으로 문자열 number의 각 숫자를 차례로 확인하면서 스택(answer)에 숫자를 추가한다. 이때 현재 숫자가 스택의 마지막 숫자보다 크면, 그 스택의 마지막 숫자를 제거한다. 이렇게 하면 큰 숫자가 더 높은 자리에 오도록 조정할 수 있다.
2. 숫자를 제거할 때마다 k를 1씩 감소시킨다.
3. 모든 숫자를 처리한 후, 스택에 남은 숫자를 모두 이어붙여 최종 결과를 만든다.

시간 복잡도

O(n) (n: 문자열 number의 길이)

---

회고

저번에 스택큐 문제 풀 때 스택 정리를 못하고 넘어간 것 같기 때문에 이참에 스택 정리하기~

스택

• 후입선출(LIFO, Last In First Out) 구조를 가진 자료구조. 마지막에 들어간 요소가 가장 먼저 나온다.
• 사용 사례
  • 괄호 검사: 괄호가 올바르게 짝을 이루는지 확인할 때 사용
  • 수식 계산: 중위표기법을 후위표기법으로 변환하거나 계산할 때 사용
  • 깊이 우선 탐색(DFS)
• 기본 연산
  • push(x): 스택의 맨 위에 요소 'x' 추가
  • pop(): 스택의 맨 위 요소를 제거하고 반환, pop(i)의 경우 i번째 인덱스 원소 리턴하고 삭제
  • peek(): 스택의 맨 위 요소를 제거하지 않고 반환
  • isEmpty(): 스택 비어있는지 확인