[프로그래머스] 42883번 / Java / 큰 수 만들기

문제 - (https://programmers.co.kr/learn/courses/30/lessons/42883)

그리디 문제다.

k만큼 제거하는 것이므로 number의 길이에서 k를 뺀 만큼의 길이가 정답 문자열의 길이가 됨을 알아야 한다.

 

예를 들어,

number.length()가 7이고, k=3이면

answer.length() = 4 여야 할 것이다.

따라서

ㄱ. 첫 반복문 실행 시,

number의 0 인덱스부터 3 인덱스까지 중 가장 큰 수를 선택한다.

answer.append( 선택한 수 )

 

ㄴ. 두 번째 반복문 실행 시,

'ㄱ'에서 선택한 가장 큰 수의 다음 인덱스부터 4 인덱스까지 중 가장 큰 수를 선택한다.

answer.append( 선택한 수 )

 

ㄷ. 세 번째 반복문 실행 시,

'ㄴ'에서 선택한 가장 큰 수의 다음 인덱스부터 5 인덱스까지 중 가장 큰 수를 선택한다.

answer.append( 선택한 수 )

 

... 이렇게 반복하다가 answer.length() == 4가 되는 시점에서 종료하면 된다.

---

📌주의할 점

• char형을 int로 변환하는 방법은 크게 두 가지이다.
  char ch = '3'
  1. Character.getNumericValue(ch)
  2. ch - '0'
  처음에 나는 1번을 사용했는데 시간초과가 발생했다. 2번으로 변경하니 통과했다.
  char형에 - '0'를 해주는 방법이 더 빠르니 앞으로 이걸 사용하도록 해야겠다.

---

😅실수

• 설계를 머릿속으로 하고 바로 코드로 옮기는 바람에 시행착오를 많이 겪었다. 설계를 반드시 완벽히 하고 코드로 옮기자.
• 반복문 시작 및 종료 시점이 헷갈릴 때는 반복문의 진행 과정을 일일이 써보면서 규칙을 찾자.

 

---

코드

public class MakeBigNumber {
    static String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();

        int size = number.length();

        int start = 0;
        int cnt = size - k;
        int end = size - cnt; /* 여기를 생각 못함 */

        while (true) {
            if (answer.length() == size - k) break;
            int idx = start;
            int bigger = -1;
            for (int i = start; i <= end; i++) {
                // 가장 큰 수 찾기
                if (i >= number.length()) break;
                /* char형을 int로 변환할 때 좀 더 빠른 방법은 2번이다*/
                /*1*///int cur = Character.getNumericValue(number.charAt(i));
                /*2*/int cur = number.charAt(i) - '0';
                if (bigger < cur) {
                    bigger = cur;
                    idx = i;
                }
            }
            answer.append(bigger);
            start = idx + 1;
            end = size - --cnt;
        }

        return answer.toString();
    }

    public static void main(String[] args) {
        String number = "1924";
        int k = 2;
        String number2 = "1231234";
        int k2 = 3;
        String number3 = "4177252841";
        int k3 = 4;

        System.out.println(solution(number, k));
        System.out.println(solution(number2, k2));
        System.out.println(solution(number3, k3));
    }
}