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

코딩테스트 연습 - 큰 수 만들기 | 프로그래머스 (programmers.co.kr)

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

어떻게 생각하고 문제를 풀었는가?

탐욕 알고리즘을 사용하고자 했습니다.

탐욕 알고리즘이란 주어진 상황에서 최적을 선택해나가 답을 구하는 알고리즘입니다.

고려 대상에 두개의 문자만을 두고 앞 자리의 수가 뒷 자리의 수보다 클때까지 앞 자리수를 삭제하는 식으로 문제를 해결하고자 하였습니다.

중간에 삭제되는 문자가 있을 수 있습니다. 이를 고려하여 LIFO인 자료구조 Stack을 활용하고자 하였습니다.

 

코드

import java.util.Stack;
class Solution {
    public String solution(String number, int k) {
        Stack<Character> stack = new Stack<>();
        for(int i=0; i<number.length(); i++){
            char value = number.charAt(i);
            while(!stack.empty() && k>0 && stack.peek()<value){
                stack.pop();
                k--;
            }
            stack.push(value);
        }
        String answer = "";
        while(k>0){
            k--;
            stack.pop();
        }
        while(!stack.empty()){
            answer=stack.pop()+answer;
        }
        return answer;
    }
}

설계를 바탕으로 코드를 작성하였습니다.

k번의 삭제를 stack.pop함수로 구현하였으며 stack은 LIFO이므로 문자열에 출력하고자 할 때 역순으로 배치하도록 하였습니다. 

개선

import java.util.Stack;
class Solution {
    public String solution(String number, int k) {
        char[] answer = new char[number.length()-k];
        Stack<Character> stack = new Stack<>();
        for(int i=0; i<number.length(); i++){
            char value = number.charAt(i);
            while(!stack.empty() && k>0 && stack.peek()<value){
                stack.pop();
                k--;
            }
            stack.push(value);
        }
        while(k>0){
            k--;
            stack.pop();
        }
        for(int i=answer.length-1;i>=0;i--){
            answer[i] = stack.pop();
        }}
        return new String(answer);
    }
} 

위의 코드로도 테스트는 통과하였지만 큰 입력에 대해 시간적인 아웃풋이 불안했습니다.

그래서 String의 +연산을 하는 것이 아닌 char 배열에 문자들을 배치한 후 new String을 통해 리턴 값만 문자열로 전달하도록 코드를 수정하였습니다.

실행시간이 꽤 단축되었습니다.

String의 +연산

java에서 String의 +연산은 StringBuilder의 append함수로 구현되어 있습니다.

StringBuilder는 String이 같은 인스턴스 내의 문자열 변경이 가능하도록 구현된 클래스입니다.

StringBuilder의 append함수를 확인한 결과 char의 입력에도 string으로 변경한 후 문자열에 추가되는 방식으로 진행되고 있었습니다.

또한 문자열이 추가될 때 마다 길이가 증가하였으므로 기존의 코드에서 남은 문자들의 수만큼 문자열 크기 변경이 이루어지고 또한 문자열로의 형변환도 이루어졌을 것입니다.

char의 입력도 String으로 변환하는 작업을 수행한다.

이번 문제에서 문자열과 삭제해야하는 숫자의 수는 입력으로 주어지므로 결과물의 자릿수 또한 number.length() - k로 동일할 것입니다.

따라서 string으로 단순히 +연산을 하는 것보다 미리 char 배열을 만들고, index를 이용하여 배열을 완성한 후 마지막으로 문자열로 형변환을 하는 것이 좀 더 효율적임을 확인할 수 있었습니다.