[프로그래머스] 큰 수 만들기(42883)

1. 문제 풀이 아이디어

• 스택을 사용하여 숫자를 비교하며 원하는 조건에 맞는 결과를 얻을 수 있다.

2. 나의 정답 코드

class Solution {
    public String solution(String number, int k) {
        StringBuilder stringBuilder = new StringBuilder();
        char[] stack = new char[number.length()];
        int si = -1;
        int ni = 0;
        for (int i = 0; i < k; i++) {
            if (si == -1) {
                stack[++si] = number.charAt(ni++);
            }
            while (ni < number.length() && stack[si] >= number.charAt(ni)) {
                stack[++si] = number.charAt(ni++);
            }
            si--;
        }
        for (int i = 0; i <= si; i++) {
            stringBuilder.append(stack[i]);
        }
        stringBuilder.append(number.substring(ni));
        return stringBuilder.toString();
    }
}

3. 정리

• 스택이 비어있다면, number에서 문자를 하나 가져와 스택에 넣는다.

• ni가 number의 길이보다 작고 스택의 값이 현재 문자보다 크거나 같으면, 스택에 문자를 넣는 과정을 반복한다.

• 반복문을 빠져나왔을 경우, 스택의 가장 위에 있는 문자가 다음 문자보다 작다는 뜻이므로 스택에서 문자를 제거한다.

• 이러한 과정을 k번 반복한 뒤, 스택에 남아 있는 문자와 number의 나머지 문자를 결합하면 정답을 얻을 수 있다.

4. 자료구조 사용 시 시간 비교

스택 큐 사용 시

스택 배열 사용 시

배열만 사용 시

• 라이브러리 자료구조를 사용했을 때 속도가 더 느렸다.

• 최대 크기가 정해져 있을 경우, 라이브러리 자료구조보다 배열을 사용하는 것이 더 빠르다.

• 스택 큐 사용 코드

class Solution {
    public String solution(String number, int k) {
        StringBuilder stringBuilder = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        Queue<Character> queue = new ArrayDeque<>();
        for (int i = 0; i < number.length(); i++) {
            queue.add(number.charAt(i));
        }
        for (int i = 0; i < k; i++) {
            if (stack.isEmpty()) {
                stack.push(queue.poll());
            }
            while (!queue.isEmpty() && stack.peek() >= queue.peek()) {
                stack.push(queue.poll());
            }
            stack.pop();
        }
        for (Character c : stack) {
            stringBuilder.append(c);
        }
        for (Character c : queue) {
            stringBuilder.append(c);
        }
        return stringBuilder.toString();
    }
}

• 스택 배열 사용 코드

class Solution {
    public String solution(String number, int k) {
        StringBuilder stringBuilder = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        int index = 0;
        for (int i = 0; i < k; i++) {
            if (stack.isEmpty()) {
                stack.push(number.charAt(index++));
            }
            while (index < number.length() && stack.peek() >= number.charAt(index)) {
                stack.push(number.charAt(index++));
            }
            stack.pop();
        }
        for (Character c : stack) {
            stringBuilder.append(c);
        }
        stringBuilder.append(number.substring(index));
        return stringBuilder.toString();
    }
}