[JAVA]/Programmers

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

춘햄 2021. 4. 12. 09:59

엥...이거 완전...? 그냥 완전 탐색 기법을 사용해서 숫자 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 가 되는 마법이 일어났다. (진짜 미친 거 같다. 앞으론 이거만 써야겠다...)

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

반응형