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

1. 문제분석

 

순서를 유지하면서 가장 큰 수를 뽑는 문제다.

순서가 존재하므로 정렬로 하면 안되고 나는 재귀를 생각해서 2개의 숫자를 뽑은 후 가장 큰 수를 반환할려고 했다.

계속 알고리즘적으로 생각해봤는데 암만봐도 이건 아니다 싶었다.

 

그래서 다른 방면으로 생각해봤다.

만약 6자리를 뽑는다면 맨 처음 수는 어디서 뽑아야할까?

말 그대로 첫번째 자리를 위해 나머지 뒤의 숫자를 이미 정해뒀다고 생각하는 것이다.

테스트케이스 3번을 보자.

4177252841이고 4개의 숫자를 뺀다고 한다. 그러면 총 6개의 숫자를 고르는 것이다.

첫번째를 뽑고 나머지 5글자는 맨 뒤에 둔다고 하자. 4 1 7 7 2 5 2 8 4 1 가 된다.

말 그대로 첫번째 숫자는 "41772", 최소 조건을 만족하기 위해 나머지 숫자를 미리 정해둔다는 뜻이다.

 

이제 7을 뽑았으니 다음 숫자를 보자. 4 1 7 / 7 2 5 2 8 4 1 우리는 7을 뽑은 상태고 이제 다음 숫자를 보면 된다.

첫번째 숫자를 뽑았으니 이제 두번째 숫자를 뽑아보자. 마찬가지로 뒤에는 최소 4자리가 되야 6글자를 만족한다.

7이 가장 크니 7을 뽑고 이제 숫자 형태는 4 1 7 7 / 2 5 2 8 4 1가 된다.

 

위와 같은 방법으로 계속 접근하면 된다.

2. 구현

class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();
        //넣고자 하는 글자의 인덱스
        int nowIdx = 0;
        //구역에서의 최댓값
        int nowMax = 0;
        int repeat = number.length() - k;

        //원하는 글자 수 만큼 반복
        for(int i = 0; i<repeat; i++){
            nowMax = 0;
            //k는 한자리씩 늘어나야함.
            for(int j = nowIdx; j<=k+i; j++){
                //구역 내에서의 최댓값 구하기
                if(nowMax < number.charAt(j) - '0'){
                    nowMax = number.charAt(j) - '0';
                    //최댓값인 글자까지 넣었으니 다음 숫자는 현재위치 + 1
                    nowIdx = j+1;
                }
            }
            //글자 추가
            answer.append(nowMax);
        }
        return answer.toString();
    }
}

 

사실 위의 알고리즘도 오래걸렸지만 구현도 오래걸렸다.

나는 subString으로 배열을 생성해서 데이터를 선별했는데 위의 코드처럼 너무 간단하게 나와서 조금 허탈했다.

아직 Java문법도 부족한가 보다.. subString은 블로그에 정리해두겠다.

 

최대값을 찾는건 직접 다 대입해서 골랐고 찾을때 마다 idx를 갱신했다.

다음으로 i만큼 점점 좁혀져야하니 k+i를 범위로 지정했다.

3. 마무리

알고리즘을 하면 할수록 많이 부족하다는 것을 느낀다.

앞으로 더 열심히 해야겠다.