26. 큰 수 만들기

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

큰 수 만들기
탐욕법(Greedy)
3568명 완료

코딩테스트 연습 - 큰 수 만들기

파이썬

def solution(number, k):
    count, i = 0, 0
    while i < len(number) - 1:
        if number[i] < number[i+1]:
            number = number[:i] + number[i+1:]  # 이 부분이 문제...
            count += 1
            if i > 0:
                i -= 1
            if count == k:
                return number
        else:
            i += 1
    return number[:len(number) - k]

테스트 1 〉	통과 (0.04ms, 10.8MB)
테스트 2 〉	통과 (0.04ms, 10.7MB)
테스트 3 〉	통과 (0.07ms, 10.7MB)
테스트 4 〉	통과 (0.12ms, 10.7MB)
테스트 5 〉	통과 (0.35ms, 10.8MB)
테스트 6 〉	통과 (9.22ms, 10.8MB)
테스트 7 〉	통과 (37.19ms, 10.9MB)
테스트 8 〉	통과 (194.71ms, 11.1MB)
테스트 9 〉	통과 (8.19ms, 11.9MB)
테스트 10 〉	통과 (6570.72ms, 13.2MB)
테스트 11 〉	통과 (0.04ms, 10.6MB)
테스트 12 〉	통과 (0.04ms, 10.7MB)

왠지 특이하게 풀고 싶어서 문자열로 만들었더니 너무 느립니다.
스택을 쌓아봅니다. 
코드도 짧고 날아다닙니다. 정상적으로 풀어야겠습니다. 반성합니다. ㅠ,.ㅠ 

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

테스트 1 〉	통과 (0.04ms, 10.7MB)
테스트 2 〉	통과 (0.05ms, 10.7MB)
테스트 3 〉	통과 (0.06ms, 10.7MB)
테스트 4 〉	통과 (0.13ms, 10.7MB)
테스트 5 〉	통과 (0.20ms, 10.6MB)
테스트 6 〉	통과 (2.92ms, 10.8MB)
테스트 7 〉	통과 (6.75ms, 11.1MB)
테스트 8 〉	통과 (16.67ms, 11.4MB)
테스트 9 〉	통과 (38.30ms, 16.1MB)
테스트 10 〉	통과 (97.03ms, 15MB)
테스트 11 〉	통과 (0.04ms, 10.7MB)
테스트 12 〉	통과 (0.03ms, 10.7MB)

JS

function solution(number, k) {
    let stack = []
    for (let each of number) {
        while (k > 0 && stack.length > 0 && stack[stack.length-1] < parseInt(each)) {
            stack.pop()
            k--
        }
        stack.push(parseInt(each))
    }
    return stack.slice(0, number.length-k).join("")
}

테스트 1 〉	통과 (1.72ms, 37.4MB)
테스트 2 〉	통과 (1.64ms, 37.4MB)
테스트 3 〉	통과 (1.70ms, 37.3MB)
테스트 4 〉	통과 (1.96ms, 37.8MB)
테스트 5 〉	통과 (2.02ms, 37.7MB)
테스트 6 〉	통과 (6.42ms, 37.8MB)
테스트 7 〉	통과 (11.08ms, 39.8MB)
테스트 8 〉	통과 (13.68ms, 40.9MB)
테스트 9 〉	통과 (39.70ms, 52.7MB)
테스트 10 〉	통과 (42.07ms, 50.5MB)
테스트 11 〉	통과 (1.62ms, 37.7MB)
테스트 12 〉	통과 (1.90ms, 37.6MB)

Java

class Solution {
    public String solution(String number, int k) {
        var result = new StringBuilder();
        for (var each : number.toCharArray()) {
            while (result.length() > 0 && k > 0 && result.charAt(result.length() - 1) < each) {
                k--;
                result.deleteCharAt(result.length() - 1);
            }
            result.append(each);
        }
        return result.substring(0, Math.min(result.length(), result.length() - k));
    }
}