[JAVA] Programmers <Greedy LV2> 큰 수 만들기

엥...이거 완전...? 그냥 완전 탐색 기법을 사용해서 숫자 2자리를 제외하고 나머지를 사용하여 수열을 뽑아내면 되는 문제 아닌가..? 

그래서 이전에 사용했던 조합을 뽑는 알고리즘을 그대로 가져와 조합을 뽑고, Integer 리스트에 넣어서 정렬하여 가장 큰 수를 뽑아내는 방식으로 코드를 작성했는데,

---

package com.choonham;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
	private  List<Integer> strArray = new ArrayList<Integer>();
    public String solution(String number, int k) {
        String answer = "";
        List<Integer> inputArray  = new ArrayList<Integer>();
        List<Integer> resultArray  = new ArrayList<Integer>();

        for(int i = 0; i < number.length(); i++) {
        	if(i == number.length()-1) inputArray.add(Integer.parseInt(number.substring(number.length()-1)));
        	else inputArray.add(Integer.parseInt(number.substring(i, i+1)));
        }
        
        if(inputArray.size() - k == 0) return answer = "0";
        getCombination(inputArray, resultArray, 0, inputArray.size(), inputArray.size() - k);
        Collections.sort(strArray, Collections.reverseOrder());
        
        answer = Integer.toString(strArray.get(0));
        return answer;
    }
    
    private void getCombination(List<Integer> inputArray, List<Integer> resultArray, int start, int inputLen,
			int num) {
    	
		if (num == 0) {
			String tempStr = "";
			for(Integer i : resultArray) {
				tempStr += i;
			}
			int tempInt = Integer.parseInt(tempStr);
			this.strArray.add(tempInt);
			return;
		}
		
		for (int i = start; i < inputLen; i++) {
			resultArray.add(inputArray.get(i)); // visited의 역할, 현재 값을 삽입 후
			getCombination(inputArray, resultArray, i + 1, inputLen, num - 1); 
			// 현재 인덱스 + 1, 출력 자리수 -1을 한 뒤, 재귀를 한번 진행한 후
			resultArray.remove(resultArray.size() - 1); // 현재 값 제거
		}
	}
}

리스트를 만들고 다시 정렬 후에 변환하는 과정이 조금 복잡하긴 하다. 근데 질문 게시판에 모든 테케를 다 통과했으니... 시간 초과가 아니라면 안될 이유는 없다고 생각했다.

...? 무려 런타임 에러;; 이건 뭐가 틀렸는 지 진짜 모르겠다... 추측하건데, 아마 Integer값으로 정렬을 한 뒤에 다시 String 값으로 변환하는 과정에서 수의 범위가 Integer, Long의 범위를 넘어가면 에러가 나오긴 하는데... 애초에 그 정도 길이로 예제를 주면 시간 초과가 나올 게 뻔하기 때문에 그냥 Greedy 방식으로 진행하려고 한다. 

---

앞에 있는 수 부터 차례차례 뽑아 가장 큰 수를 조합해야하니, 사이클은 number.length - k 개의 수를 뽑아내며, number.length - k 번째의 수부터는 첫 사이클에서 뽑아선 안된다. (그럼 조합을 완성을 못시키므로) 

즉, 0부터 number.length - k 까지 반복문을 돌리며 max값을 찾아내고, max값의 위치부터 다음 반복문을 돌리면 구할 수 있다.

---

package com.choonham;


class Solution {
    public String solution(String number, int k) {
        String answer = "";
        for (int j = 0, index = -1; j < number.length() - k; j++) {
            char max = 0;
            for (int i = index + 1; i <= k + j; i++) {
                if (max < number.charAt(i)) {
                    index = i;
                    max = number.charAt(i);
                }
            }
            answer += max;
        }
        return answer;
    }
}

 

돌려보면,

실패한다. (아오....)

찾아보니, 시간 단축 최대 꼼수인 StringBuilder를 사용하면 통과된다고 한다.  

바로 해보자.

---

package com.choonham;


class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();
        for (int j = 0, index = -1; j < number.length() - k; j++) {
            char max = 0;
            for (int i = index + 1; i <= k + j; i++) {
                if (max < number.charAt(i)) {
                    index = i;
                    max = number.charAt(i);
                }
            }
            answer.append(max);
        }
        return answer.toString();
    }
}

이젠 되겠지??

9166ms -> 27.29ms 가 되는 마법이 일어났다. (진짜 미친 거 같다. 앞으론 이거만 써야겠다...)

근데 사실, 아직도 조합을 뽑아서 변환해주는 코드가 왜 실패한 지 모르겠다....이번 문제는 질문 게시판 어디에도 반례를 찾을 수가 없어서...아침부터 굉장히 스트레스를 많이 받은 문제였다...