프로그래머스 - 큰 수 만들기 (sol.java)

◎문제 링크

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

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

---

 

 

 

◎문제 파악

숫자 1924에서 수 한개를 제거할때 만들 수 있는 가장 큰 수는 924이다.

숫자 924에서 수 한개를 제거할때 만들 수 있는 가장 큰 수는 94이다.

 

숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있다. 이 중 가장 큰 숫자는 94 이다.

 

=> 숫자 K개를 제거해야 한다면, 숫자 한개를 제거하여 가장 큰수를 만드는 과정을 K번 반복하면 된다.

---

◎숫자 한개를 제거하여 가장 큰수를 만드는 과정

 

1)"124"에서 한개를 제거하여 가장 큰수를 만드는 법은 1을 제거하는 것이다.

=> index 0이 index1보다 작다면,index0을 삭제하는게 가장 큰수를 만드는 방법이다.

 

2)"953"에서 한개를 제거하여 가장 큰수를 만드는 법은 3을 제거하는 것이다.

3)"924"에서 한개를 제거하여 가장 큰수를 만드는 법은 2을 제거하는 것이다.

=> index 0이 index1보다 크다면, index 1과 2를 비교하여 더 작은 수를 제거한다.

 

∴앞에서부터 i번째 인덱스와 i+1번째 인덱스를 비교하여,

i번째 인덱스가 i+1번째 인덱스보다 작으면,i번째 인덱스를 제거,

그렇지 않으면, i+1번째 인덱스와 i+2번째 인덱스를 비교하는 과정을 반복한다.

 

전체 코드:

class Solution {
    public String solution(String number, int k) {
        
        StringBuilder num = new StringBuilder(number); //StringBuilder 생성
        
        int i = 0;//인덱스 변수 i
        
       for(int j = 0; j<k; j++){
           i=0;
           int len = num.length()-1;
           while(i< len){
               if((int)num.charAt(i) < (int)num.charAt(i+1)){ 
                   //i번째 인덱스가 i+1번째 인덱스보다 작으면, i번째 인덱스 삭제
                   num.delete(i,i+1);
                   break;
               }
               else{
                   //그렇지 않으면, i+1번째 인덱스와 i+2번째 인덱스 비교
                   i++;
               }
           }
           
           if(i==len){
               num.delete(i,i+1);
           }
       }
        
        
        String answer = num.toString();
        return answer;
    }
}

※StringBuilder class: kkwong-guin.tistory.com/37

Java - StringBuilder/StringBuffer 클래스, 메서드

11번째 줄의 while문과 23번째 줄의 if 문은 맨 마지막 인덱스가 가장 작은 숫자일경우 제거하기 위해 쓰여졌다.

 

---

◎다른 사람의 풀이

import java.util.Stack;
class Solution {
    public String solution(String number, int k) {
        char[] result = new char[number.length() - k];
        Stack<Character> stack = new Stack<>();//Stack클래스 선언

        for (int i=0; i<number.length(); i++) {
            char c = number.charAt(i);
            while (!stack.isEmpty() && stack.peek() < c && k-- > 0) {
                //1.stack이 비어있지 않고,
                //2.stack의 맨 위 값(index:i-1)이 현재값(index:i)보다 작고,
                //3.k--가 0보다 클때
                stack.pop(); //맨위의 stack 값을 삭제한다.
            }
            stack.push(c);
        }
        for (int i=0; i<result.length; i++) {
            result[i] = stack.get(i);
        }//맨 마지막 숫자가 제일 작은경우 stack에는 집어 넣지만. i<result.length제한으로 result에는 포함이 되지 않는다.
        return new String(result);
    }
}

ex)

number: "1942" k=2

① stack에 1추가 (stack: 1)

② while문을 만족하므로, stack.pop() (stack: empty)

③ stack에 9 추가 (stack: 9)

④ while문을 만족하지 못함 

⑤ stack에 4 추가 (stack: 9,4)

⑥ while문을 만족하지 못함 

⑦ stack에 2추가 (stack: 9,4,2)

⑧ result.length == 2이므로 return되는 result 값은 94