[프로그래머스] 큰 수 만들기 - Java

문제 설명

 

프로그래머스

 

접근 방법

해당 문제에서는 특정 수가 문자열로 주어졌을 때 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 요구하고 있습니다.

 

제가 접근했었던 방법은 주어진 문자열을 순회하면서 앞선 숫자가 뒤에 나오는 숫자보다 작을 경우 해당 숫자를 지워나가는 방식으로 접근하는 것이었습니다. 이때 뒤에 나오는 숫자보다 앞선 숫자가 더 크다면 제거할 수 있는 수(k)의 여분이 있는 경우에 대해서만 추가적으로 뒤에 나오는 숫자들을 탐색하도록 했고 이때 나오는 숫자 보다 작다면, 앞선 숫자를 제거하였습니다. 

 

다만, 이럴 경우 주어진 수가 내림차순으로 구성된 수라면 어떤 수도 제거하지 못하게 되므로 한번도 제거하지 못했을 경우 별도로 해당 수의 역순으로 탐색하면서 수를 제거하도록 처리했습니다.

 

하지만 제가 작성한 로직의 경우 이를 단순히 for 문과 if 문의 조합으로 구현했었는데, 이럴 경우 다소 불필요한 연산이 많이 발생하는 문제가 있었습니다.

 

해당 문제에 대해서 개인적으로 모범 답안이라고 생각했었던 다른 사람의 풀이를 참고하였는데, 해당 접근 방식으로는 스택을 이용하는 것이었습니다. 스택을 이용한다면 앞선 숫자를 스택의 peek 메서드로 표현할 수 있습니다. 아울러, 이 peek 값 보다 뒤에 나오는 숫자가 더 클 경우 pop 메서드를 통해 앞선 숫자를 손쉽게 제거할 수 있습니다. 더욱이 앞선 숫자가 뒤에 나오는 숫자보다 크다면 뒤에 나오는 숫자를 단지 스택에 push 해주기만 하면 됩니다.

 

문자열, 배열 등 연속된 데이터 상에서 앞쪽 데이터와 뒤쪽 데이터를 일일이 비교하는 연산 처리 시에는 스택을 적극적으로 활용해봐야겠다는 생각이 들었습니다. 😂

 

 

전체 소스 코드

나의 풀이

    public String solution(String number, int k) {
        char[] bits = number.toCharArray();
        int length = bits.length;
        boolean[] selected = new boolean[length];

        boolean flag = true;
        char present = bits[0], target;

        int count = k, index;
        for (int i = 1; i < length; i++) {
            target = bits[i];

            if (present < target) {
                selected[i - 1] = true;
                count--;
                flag = false;
            } else {
                index = count;
                for (int j = i + 1; j < length && index > 0; j++) {
                    target = bits[j];
                    if (present < target && j - i + 1 <= count) {
                        selected[i - 1] = true;
                        count--;
                        flag = false;
                        break;
                    }
                    index--;
                }
            }

            if (count == 0) {
                break;
            }

            present = bits[i];
        }

        if (flag) {
            for (int j = length - 1; j > -1 && count > 0; j--) {
                selected[j] = true;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length; i++) {
            if (!selected[i]) {
                sb.append(bits[i]);
            }
        }

        return sb.toString();
    }

 

모범 답안(다른 사람 풀이)

import java.util.Stack;

class Solution {
    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.isEmpty() && 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);
    }
}

 

 

참고자료

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