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

programmers.co.kr/learn/courses/30/lessons/42883

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

 

이 문제는 스택(Stack) 자료구조를 통해 해결할 수 있었습니다.

 

1. 전체 문자를 하나씩 확인하면서

2. stack이 비어있지 않다면 stack의 마지막 문자와 현재 문자를 비교하여 마지막 문자가 더 작은 경우 삭제해야하는 문자의 수가 아직 남은 경우 stack에서 마지막 문자를 삭제합니다. 이 조건을 반복적으로 확인합니다.

3. 문자를 삭제하는 반복이 끝나면 현재 문자를 stack에 저장합니다.

4. 최종적으로 stack에 저장된 문자를 앞에서부터 확인하면서 (전체 문자 - 삭제해야하는 문자의 수) 길이만큼을 선택해 반환합니다.

 

예제를 통해 살펴보겠습니다.

 

자바 코드는 다음과 같습니다.

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 cur = number.charAt(i);  // 해당 위치의 문자를 뽑아
            // 스택이 비어있지 않고 마지막으로 추가된 문자가 현재 문자보다 작으면
            // 이 문자를 삭제할 수 있는 경우(아직 k개 문자가 다 삭제되지 않은 경우)
            while (!stack.isEmpty() && stack.peek() < cur && k-- > 0) {
                stack.pop();  // 스택의 마지막 문자 삭제
            }

            // 현재 문자 추가하기
            stack.push(cur);
        }

        // 스택에 담긴 문자를 배열에 앞에서부터 저장
        for (int i = 0; i < answer.length; i++) {
            answer[i] = stack.get(i);
        }

        return new String(answer);
    }
}