[프로그래머스] - 큰 수 만들기(그리디 Lv.2) - Java

https://school.programmers.co.kr/learn/courses/30/lessons/42883?language=java

프로그래머스

문제

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

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

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

접근

• 숫자들의 순서는 바뀔 수 없고, 결국 빼고 남은 수 중에 가장 큰 수를 구해야 하는 문제
• 3번째 예시에서 "4177252841" 에서 4개를 빼야 하므로
  • 앞의 4개를 뺀다고 하면 "252841"이 남으므로 맨 앞자리에 들어갈 수 있는 수는 "41772"중 하나이다.
  • 즉, 앞에서부터 5개씩 잘라서 가장 큰 수를 찾고,
  • 찾아낸 큰 수 앞에 위치한 수는 이미 필요 없으므로 탐색에서 제외

	비교할 문자열	가장 큰 수
4177252841	41772	7
4177252841	17725	7
4177252841	77252	5
4177252841	72528	8
4177252841	25284	4
4177252841	52841	1
775841

 

 

풀이 코드

class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();
        char[] numArray = number.toCharArray();
        int lenAnswer = number.length() - k; // 결과
        int startIndex = 0;

        // 문자열의 길이가 lenAnswer이 될 때 까지 while
        while (startIndex < number.length() && answer.length() != lenAnswer){
            int endNum = k + answer.length() ; // 최댓값 찾는 숫자 갯수
            int maxNum = 0; // 현재 최댓값
            // startIndex부터 endNum 자릿수 사이의 숫자들로 돌려서 최댓값 찾기
            for (int i = startIndex; i <= endNum; i++){
                // charAt : 리스트에서 해당 인덱스의 요소, charAt(i) - 0 : 뽑은 요소 정수로 변환하기
                // i번째 숫자와 max를 비교해서 가장 큰 걸 max에 넣기
                if (maxNum < number.charAt(i) - '0') { 
                    maxNum = number.charAt(i) - '0';
                    // 가장 큰 값 찾았으면 그 수 뒤에거부터 다시 돌기
                    startIndex = i + 1;
                }
            }
            answer.append(Integer.toString(maxNum));
        }
        return answer.toString();
    }
}