그리디/큰 수 만들기 / 스택

📕 문제

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

프로그래머스

 

 

 

 

📄 내가 생각한 풀이

# 1. 모든 조합: len(number) - k 개 숫자에서 나올 모든 조합
# 2. sort()로 정렬
# 3. max함수로 가장 큰 수 찾기

 

💻 내 코드

 

from itertools import combinations

def solution(number, k):
 
    
    x = len(number) - k
    
    
    num_list = list(combinations(number, x))
  

    # print(num_list)
    
    answer = max(''.join(i) for i in num_list)
    
                    
                                 
    return answer

조합 사용해서 풀었는데 시간초과로 실패

-> 스택사용하기

max함수 사용하면 sort 사용할 필요 없음

 

 

 

 

💻 답안

def solution(number, k):
    stack = []  # 결과를 저장할 스택
    
    for num in number:
        # 스택의 마지막 숫자가 현재 숫자보다 작고, 제거할 기회(k)가 남아 있다면 제거
        while stack and k > 0 and stack[-1] < num:
            stack.pop()
            k -= 1
        # 현재 숫자를 스택에 추가
        stack.append(num)
    
    # k가 남아있다면 뒤에서부터 제거
    if k > 0:
        stack = stack[:-k]
    
    # 스택을 문자열로 변환
    return ''.join(stack)

 

 

설명

1. 루프 동작:
   • 숫자를 하나씩 처리하며 스택에 넣습니다.
   • 넣기 전에 스택의 마지막 숫자와 비교하여, 현재 숫자가 더 크면 스택의 숫자를 제거합니다.
   • 제거는 k번까지만 가능합니다.
2. k가 남아있는 경우:
   • 루프가 끝난 뒤에도 k가 남아있다면, 스택의 뒤에서 k만큼 숫자를 제거합니다.
3. 최종 결과:
   • 스택에 남아있는 숫자를 문자열로 합쳐 결과를 반환합니다.

 

---

동작 과정 예시

Input: "1924", k = 2

1. 초기 상태: stack = [], k = 2
2. 첫 번째 숫자 '1': stack = ['1']
3. 두 번째 숫자 '9':
   • '9' > '1', stack.pop(), k = 1
   • stack = ['9']
4. 세 번째 숫자 '2': stack = ['9', '2']
5. 네 번째 숫자 '4':
   • '4' > '2', stack.pop(), k = 0
   • stack = ['9', '4']
6. 결과: '94'

 

 

 

📁 참고자료

 

☺️ 새로 알게 된 지식

장점

• 조합을 사용한 방식은 비효율적으로 모든 경우의 수를 탐색하지만, 스택을 사용하면 한 번의 순회로 문제를 해결합니다.
• O(n)O(n) 시간 복잡도를 가지므로 대규모 입력에도 효율적입니다.

 

😉 리뷰

 

스택 구현 익히기