[99클럽 코테 스터디 20일차 TIL] 큰 수 만들기 - Java [자바][프로그래머스]

 

 

📜 문제 내용

 

🤔 과정

• 순서대로 문자열 앞부터 순회하면서, 큰 수가 나오면 작은 값을 계속 삭제하는 것이 포인트. 
  • 1 -> 9 (1을 버리고 9를 넣음) -> 2 -> 4 (2를 버리고 4를 넣음) 
• 문자열 number를 char 형태로 쪼개 하나씩 Character 형 stack에 조건에 맞게 넣는다. 

 

✨ 최초 제출 답안 -  🆖 테스트케이스 오답 

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        
        Stack<Character> stack = new Stack<>();

        for(int i = 0; i < number.length(); i++){
            char num = number.charAt(i);
            while(!stack.isEmpty() && stack.peek() < num && k > 0){
                k--;
                stack.pop();
            }
            stack.add(num);
        }

        String answer = "";
        for(int i=0;i<stack.size();i++){
            answer += stack.get(i);
        }
        
        return answer;
    }
}

 

• 반례가 어떤 것이 있을까 고민했고, 계속 줄어드는 숫자(ex. 4321) 의 경우에 스택에 모든 숫자들이 다 들어가있어서 stack.size()로 제한하면 모든 숫자가 그대로 answer에 들어가게 된다. 

반례 1) ("1000", 1)
기댓값 : "100" , 실제 나온 값 "1000"

반례 2) ("4321", 1)
기댓값 : "432" , 실제 나온 값 "4321" 

• 그래서 StringBuilder로 answer를 만든 뒤, 나중에 substring을 통해 잘라내기로 해봤다. 

 

✍️ 재제출 답안

import java.util.*;

class Solution {
    public String solution(String number, int k) {

        Stack<Character> stack = new Stack<>();

        for(int i = 0; i < number.length(); i++){
            char num = number.charAt(i);
            
            while(!stack.isEmpty() && stack.peek() < num && k > 0){
                k--;
                stack.pop();
            }
            
            stack.add(num);
        }

        StringBuilder answer = new StringBuilder();
        for(int i = 0; i < stack.size(); i++){
            answer.append(stack.get(i));
        }
        
        return answer.substring(0, answer.length() - k);
    }
}

 

 

🔗 문제 링크

• 프로그래머스 - 큰 수 만들기 (링크) 

프로그래머스