[프로그래머스][Java][Lv. 2] 큰 수 만들기

문제 설명

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

---

제한 사항

---

입출력 예

---

풀이

import java.util.PriorityQueue;
import java.util.Collections;

class Solution {
    public String solution(String number, int k) {
        PriorityQueue<String> preNums = new PriorityQueue<>(Collections.reverseOrder());
        StringBuilder answer = new StringBuilder();
        
        for (int i = 0; i < k + 1; i++) 
            preNums.add(number.substring(i, i + 1));
        number = number.substring(k + 1, number.length());
        
        String max = preNums.poll();
        answer.append(max);
        while (max.equals(preNums.peek())) {
            answer.append(preNums.poll());
        }
        k -= preNums.size();
        
        for (int i = 0; k > 0 && i < number.length() - 1;) {
            char num1 = number.charAt(i);
            char num2 = number.charAt(i + 1);
            
            if (num1 > num2) {
                number = number.replaceFirst(String.valueOf(num2), "");
                k--;
            } else i++;
        }
        answer.append(number);
        return answer.toString().replace("^0+", "");
    }
}

ㄴ 테스트케이스만 통과하는 코드

 

import java.util.Stack;

class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();
        Stack<Character> nums = new Stack<>();
        
        for (int i = 0; i < number.length(); i++) {
            char n = number.charAt(i);
            
            if (nums.isEmpty()) nums.push(n);
            else {
                while (!nums.isEmpty() && nums.peek() < n) {
                    nums.pop();
                    if (--k < 1) break;
                }
                nums.push(n);
            }
            if (k < 1) {
                number = number.substring(i + 1, number.length());
                break;
            }
        }
        
        if (k > 0) {
             while (k != 0) {
                nums.pop();
                k--;
            }
            number = "";
        }
        
        while (!nums.isEmpty()) {
            answer.append(String.valueOf(nums.pop()));
        }
        answer.reverse();
        answer.append(number);
        
        return answer.toString();
    }
}

ㄴ 모두 통과한 코드

---

후기

처음에 생각을 잘못해서 몇 번 틀렸다. k만큼 반복하며 큰 수를 구하고 그 뒤의 number 부분에서 작은거를 빼는 식으로 했는데 k만큼 반복할 때 없앴던 수가 답에 포함되는 경우가 있었다. 그래서 이 방법은 포기하고 다른 방법을 생각해봤는데 그냥 스택으로 풀기로 했다. 뒤로 한 글자씩 이동하면서 큰 수만 남기고 끝까지 갔을 때까지 k개 만큼 없애지 못했다면 스택에서 빼는 처리를 해주면 된다. 이 때는 어차피 숫자 순서는 정해져 있으니 그냥 단순히 일의 자리 부분부터 숫자 크기에 상관없이 빼주면 된다.