큰 수 만들기

2026.07.03

문제 풀이

1차 실행 오류

---

25.0/100
런타임 에러, 메모리 초과

number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.

라는 제한 조건에 의해 int, long 둘 다 사용이 불가능함

---

class Solution {
    private int n = 0;
    public void dfs(StringBuilder number, int k, int count) {
        if (count > k) {
            return;
        }
        int len = number.length();
        String sn = number.toString(); // number의 값을 복사하여 저장
        StringBuilder sbn;
        
        for (int i = 0; i < len; i++) {
            sbn = new StringBuilder(sn);
            if (count == k) {
                n = Math.max(n, Integer.parseInt(sbn.toString()));
            }   
            sbn.deleteCharAt(i);
            dfs(sbn, k, count + 1);
        }
    }
    public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder(number);
        dfs(sb, k, 0);
        
        return Integer.toString(n);
    }
}

나의 코드 + AI 활용

소요 시간: 1시간 22분

시간 복잡도: $O(n)$

---

AI를 통해 int, long을 통한 값 비교 방식은 불가능하다는 것을 깨달음

자릿수와 값에 대한 차이를 깨달았음

10자리수 범위를 가진 값에 대해 

인덱스는 10
값은 9,999,999,999 까지 나타낼 수 있기 때문에

int와 long으로는 1,000,000자리를 갖는 수를 표현할 수 없음

---

pop(): 가장 위에 위치한 원소를 꺼내지만, 비어있다면 NoSuchElementException
poll(): 똑같이 가장 위에 위치한 원소를 꺼내지만, 비어있다면 null

---

AI를 통해 구현 방식을 추천받고 해당하는 코드를 직접 작성함

스택(또는 큐)를 더 적극적으로 활용해야 겠다는 생각을 함

---

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public String solution(String number, int k) {
        Deque<Character> stack = new ArrayDeque<>();
        
        for (char c : number.toCharArray()) {
            while(!stack.isEmpty() && k > 0 && stack.peek() < c) {
                stack.pop();
                k--;
            }
            stack.push(c);
        }
        while(k > 0) {
            stack.pop();
            k--;
        }
        
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()) {
            sb.append(stack.pollLast());
        }
        
        return sb.toString();
    }
}

AI 코드

시간 복잡도: $O(n)$

---

StringBuilder를 스택처럼 활용하여
객체에 대한 오토박싱/언박싱 오버헤드를 제거

length()를 통한 스택처럼 활용이 가능하다는 점을 깨닫게 되었음

---

class Solution {
    public String solution(String number, int k) {
        StringBuilder stack = new StringBuilder();

        for (char c : number.toCharArray()) {
            while (stack.length() > 0 && k > 0 && stack.charAt(stack.length() - 1) < c) {
                stack.deleteCharAt(stack.length() - 1);
                k--;
            }
            stack.append(c);
        }

        if (k > 0) {
            stack.setLength(stack.length() - k);
        }

        return stack.toString();
    }
}