[코딩테스트] 큰 수 만들기

문제

---

큰 수 만들기 문제 바로가기

제출 코드(JAVA)

---

첫번째 코드 제출

public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder();

        int cnt = number.length() - k;
        int left = 0;
        int right = number.length() - cnt;
        int max = -1;
        int idx = 0;

        while(cnt > 0) {
            max = -1;
            for(int j = left ; j <= right ; ++j){
                int num = number.charAt(j) - '0';
                if(num > max){
                    idx = j;
                    max = num;
                }
            }
            sb.append(number.charAt(idx));
            left = idx + 1;
            right = number.length() - --cnt;
        }

        return sb.toString();
    }

핵심은 현재보다 다음 수가 더 클 시, 삭제
상수 비교가 아닌 포인터를 활용한 문자열 비교

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (0.06ms, 53.1MB)
테스트 2 〉	통과 (0.04ms, 51.8MB)
테스트 3 〉	통과 (0.06ms, 52.9MB)
테스트 4 〉	통과 (0.23ms, 52.8MB)
테스트 5 〉	통과 (2.56ms, 52.2MB)
테스트 6 〉	통과 (17.73ms, 52.4MB)
테스트 7 〉	통과 (34.29ms, 52.9MB)
테스트 8 〉	통과 (148.14ms, 56MB)
테스트 9 〉	통과 (25.40ms, 57.8MB)
테스트 10 〉	통과 (5133.97ms, 57.4MB)
테스트 11 〉	통과 (0.03ms, 52.5MB)
테스트 12 〉	통과 (0.04ms, 52.7MB)

두번째 코드 제출

public String solution(String number, int k) {
        char[] result = new char[number.length() - k];
        
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < number.length(); i++) {
            char c = number.charAt(i);
            while (!stack.empty() && stack.peek() < c && k-- > 0) {
                stack.pop();
            }
            stack.push(c);
        }

        for (int i=0; i<result.length; i++) {
            result[i] = stack.get(i);
        }
        return new String(result);
    }

스택을 활용하여 풀어낸 방식

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (0.28ms, 52.5MB)
테스트 2 〉	통과 (0.31ms, 53MB)
테스트 3 〉	통과 (0.44ms, 52.3MB)
테스트 4 〉	통과 (1.23ms, 53.6MB)
테스트 5 〉	통과 (1.91ms, 53.3MB)
테스트 6 〉	통과 (9.75ms, 52.6MB)
테스트 7 〉	통과 (28.12ms, 55.1MB)
테스트 8 〉	통과 (31.08ms, 54.8MB)
테스트 9 〉	통과 (48.37ms, 61MB)
테스트 10 〉	통과 (85.41ms, 60.9MB)
테스트 11 〉	통과 (0.25ms, 52.4MB)
테스트 12 〉	통과 (0.22ms, 52.2MB)

제출 코드(Python)

---

코드 제출

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

        answer.append(n)

    result = ''
    for i in range(len(number) - k):
        result += answer[i]

    return result

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.02ms, 10.3MB)
테스트 3 〉	통과 (0.05ms, 10.2MB)
테스트 4 〉	통과 (0.30ms, 10MB)
테스트 5 〉	통과 (0.41ms, 10.2MB)
테스트 6 〉	통과 (6.75ms, 10.1MB)
테스트 7 〉	통과 (15.33ms, 10.6MB)
테스트 8 〉	통과 (28.69ms, 10.6MB)
테스트 9 〉	통과 (69.67ms, 13.6MB)
테스트 10 〉	통과 (144.89ms, 13.3MB)
테스트 11 〉	통과 (0.01ms, 10.2MB)
테스트 12 〉	통과 (0.01ms, 10.1MB)