[프로그래머스] 큰 수 만들기- python, java (레벨 2)

 

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

프로그래머스

풀이

문제를 보았을때 알수있는 힌트

k개수 만큼 뺐을때 가장 큰수를 만드는 문제이다.

순조부를 이용하여 모든 경우의 수를 이용할수도 있겠지만 제한 조건에 1000000자리 수가 있다고하니.. 순열, 조합을 이용하면 시간 초과가 날것이다.

그렇기에 다른 방식으로 문제를 풀어야한다.

간단하게 스택 구간을 만들고 그 안에 큰 값을 계속 담게 하고 그보다 큰 값이 나오면 변경해주는 식으로 문제를 풀어주면 된다.

 

파이썬

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

자바

import java.util.Stack;

class Solution {
    public String solution(String number, int k) {
        Stack<Integer> stack = new Stack<>();
        String[] number_list = number.split("");
        StringBuffer br = new StringBuffer();
        int result_count=number_list.length-k;
        stack.add(Integer.parseInt(number_list[0]));
        for(int num =1; num<number_list.length;num++){
            while(stack.size()>0 && stack.get(stack.size()-1)<Integer.parseInt(number_list[num]) && k>0){
                k-=1;
                stack.pop();
            }
            stack.add(Integer.parseInt(number_list[num]));
        }
        for(int i=0;i<result_count;i++){
            br.append(stack.get(i));
        }
        String answer = br.toString();
        return answer;
    }
}

https://github.com/dydwkd486/coding_test/tree/main/programmers/java

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리