[Javascript][Python] 프로그래머스 LV2 큰 수 만들기

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

프로그래머스

 

- 문제 파악

1. 입력으로 주어진 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 수를 구한다.

 

- 문제 해결 흐름

1. 입력으로 주어진 숫자의 범위가 매우 크므로 모든 경우의 수를 조합하는 풀이는 아닐 것이다.

2. 스택 자료구조를 사용하여 주어진 숫자를 순회하며 스택의 마지막 요소와 순회 중인 숫자를 비교한다.

3. 스택의 마지막 요소가 더 클 경우 순회 중인 숫자를 스택에 삽입

4. 스택의 마지막 요소가 더 작을 경우 pop하고 순회 중인 숫자를 스택에 삽입

 

 

Python

def solution(number, k):
    stack = []
    
    for num in number:
        while k > 0 and len(stack) > 0 and stack[-1] < num:
            stack.pop()
            k -= 1

        stack.append(num)
    
    while k > 0:
        stack.pop()
        k -= 1

    return ''.join(stack)

Javascript 

const solution = (number, k) => {
    
    stack = [] // 자료구조 스택 사용
    
    for(let i=0; i<number.length; i++){
    	// while문 stack이 비어있지 않고 스택의 마지막 요소가 순회 중인 숫자보다 작을 경우
        while(k > 0 && stack.length > 0 && stack[stack.length-1] < number[i]){
            stack.pop()	// 스택의 마지막 요소 제거
            k -= 1
        }
        stack.push(number[i])	
    }

    while(k > 0){		// 모든 숫자를 순회했을 때, k가 0보다 클 경우 스택의 마지막 요소부터 k만큼 제거
        stack.pop()
        k -= 1
    }
    return stack.join('')
}

console.log(solution("4321", 1));