[프로그래머스] 큰 수 만들기_JAVA

문제 링크

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

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

이 문제를 보고 처음에 필자는 이렇게 생각했었다.

'조합을 이용해서 숫자를 다 뽑은 다음에, 가장 큰 수를 뽑으면 되지 않을까?'

결과는? 무수한 런타임 에러의 환영을 받았다 ㅎㅎ..

 

number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.

 

해당 제한사항 때문에 문자에서 int로 변환하는 과정에서 메모리 초과 이슈로 펑펑 터질 수밖에 없는 것이다^^..

완전탐색으로 불가능하다면 그리디(greedy)하고 탐욕스럽게 문제를 풀어야한다고 깨닫고 로직 노선을 다시 변경했다.

 

number = "4177252841", k = 4를 예시로 생각해보자.

먼저 내가 만들어야 할 수의 길이는 number.length() - k이다. 예시에서는 6자리 수
가장 큰 수가 만들어지기 위해서는 맨 앞자리의 수가 number중 가장 큰 수가 되어야 할 것이다.
단, 예시의 경우처럼 가장 큰 수 8을 맨 앞자리에 두어도, 뒤에 남은 수가 "41"로 "841" 세자리 수가 되면서 6자리수가 성립되지 못한다. (주의할 점, 이 문제를 숫자를 '지워서' 만들어야한다. 따라서 12345의 경우, 321과 같이 순서를 거스르는 방식으로 만들면 안된다! 123, 234, 345의 경우처럼 만들어야한다!!)
따라서 6자리수가 보장되도록 한 상태에서 가장 큰 수를 찾아야한다!

 

위의 문제점을 고려하여 예시를 상대로 필자의 로직대로 문제를 풀이해보자.

내가 만들어야 할 문자열은 answer = ""; 보장되어야 할 자릿수는 leftNum; 로 선언한다.

 

number = "4177252841", k = 4

• 현재 내가 뽑아야 할 숫자의 갯수는 6개로, 맨 뒤부터 5자리 수는 남겨둔다.
  (그래야 숫자 1개를 뽑더라도 뒤 5자리가 남아 무사히 6자리를 만들 수 있다.)
• "4177252841"에서 "52841"을 빼고 "41772"에서 가장 큰 수를 찾는다.
• 가장 큰 수 7을 뽑아 answer에 붙여준다. 이 때 7의 index는 2, 그 전 문자들은 다 지워준다. (순서가 중요하기 때문에 7을 뽑은이상 어차피 뒤의 숫자를 가지고 만들 수 없다.) answer ="7";
• 417을 지운 후 "7252841"에서 "2841"을 빼고 "725"에서 가장 큰 수를 찾는다.
• 7을 뽑아 붙여준다. answer = "77" 뽑은 7 이전의 숫자들은 다 버린다.
• "252841"에서 "841"을 빼고 "252"에서 가장 큰 수를 찾는다.
• 5를 뽑아 붙여준다. answer = "775" 뽑은 '5'이전의 숫자들은 다 버린다.
• "2841"에서 "41"을 빼고 "28"에서 가장 큰 수를 찾는다.
• 8을 뽑아 붙여준다. answer = "7758" 뽑은 '8'이전의 숫자들은 다 버린다.
• "41"에서 "1"을 빼고 "4"에서 가장 큰 수를 찾는다.
• 이러한 방식으로 4와 1을 붙여 answer = "775841"을 만든다.

 

예제 하나를 가지고 일일히 풀어써서 좀 장황하지만 핵심은 보장되어야 할 자릿수를 남겨두고, 나머지 부분에서 최대값을 찾아 숫자를 이어붙이는 것이다.

 

//number.length() - k 자리수만큼 구해야 한다.
//자리수가 n이라고 치면, 뒤에서 n-1개 만큼 빼고 앞에서 최댓값을 구한다.
//답에 추가하고, 그 index 기준으로 남은 자리수만큼 빼놓고 최대값을 구한다.
// + 시간때문에 StringBuilder사용하자
class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder("");
        int len = number.length() - k;
        int start = 0;
        
        while(start < number.length() && answer.length() != len) {
            int leftNum = k + answer.length() + 1;
            int max = 0;
            for (int j = start; j < leftNum; j++) {
                if (max < number.charAt(j) - '0') {
                    max = number.charAt(j) - '0';
                    start = j + 1;
                }
            }
            answer.append(Integer.toString(max));
        }
        return answer.toString();
    }
}

또한 String을 +연산으로 붙이지 말고 StringBuilder를 이용하면 수행시간을 더 줄일 수 있다.

String + String을 하게 되면 새로운 메모리를 할당하여 붙여진 결과를 넣기 때문에 메모리가 낭비되기 때문!