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

문제

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

풀이

0. 문제 해석

스택을 활용하여 풀 수 있는 문제이다.

 

1. number 문자열을 하나씩 쪼갠다.
2. stack이 비어있으면 그 문자열을 stack에 추가한다.
3. 넣을 문자열이 stack의 peek 값보다 크면 작거나 같을 때 까지 반복하여 pop하고 그 횟수를 count 한다.
4. 넣을 문자열이 stack의 peek 값보다 작거나 같으면 stack에 넣는다.
5. count를 확인하여 k만큼 pop한 경우 남은 문자열을 전부 stack에 넣는다.
6. 위 과정이 종료되었는데 count가 k보다 작은 경우 그 차이만큼 stack에서 pop 한다.

 

위 과정을 통해 나온 결과값의 역순이 정답이다.

6번 과정을 하는 이유는

 

number = 1111

k = 2

 

위와 같은 케이스가 들어올 경우

계속 같기때문에 pop과정을 넘기게되어 결과값이 1111이 되버린다. 하지만 k만큼 꼭 빼야하므로

뒤에서 pop해서 결과값이 11이 나오도록 한다.

 

1. 전체 코드

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

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        int count = 0;
        Stack<Integer> s = new Stack<Integer>();
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < number.length(); i++){            
            int value = (number.charAt(i) - '0');

            while(true){

                if(s.size() == 0){
                    s.add(value);
                    break;
                }

                if(count >= k || s.peek() >= value){
                    s.add(value);
                    break;
                }

                if(s.peek() < value){
                    s.pop();
                    count++;
                }
            }
        }

        while(count != k){
            s.pop();
            count++;
        }

        while(!s.isEmpty()){
            sb.append(s.pop());
        }

        answer = sb.reverse().toString();
        return answer;
    }
}