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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42883

코딩테스트 연습 - 큰 수 만들기 | 프로그래머스

코드

package Programmers.Level2;

import java.util.Arrays;
import java.util.Collections;

public class MakeBigNumber {

	public static void main(String[] args) {

		String number ="4177252841";
		int k = 4;

		String answer = solution2( number,k );

		System.out.println(answer);

	}//main

	public static String solution(String number, int k) {

		StringBuilder answer = new StringBuilder();

		// 최종 return값의 길이
		int size = number.length()-k;
		int cnt = size;

		StringBuilder subNum = new StringBuilder();
		StringBuilder numberBuilder = new StringBuilder(number);

		int maxIndex = 0 ;

		// 한글자씩 붙여 나간다.
		while ( answer.length() !=  cnt ) {

			// n번째 글자가 될 수 있는 후보군들.
			subNum = new StringBuilder(numberBuilder.substring( maxIndex, numberBuilder.length()-(size-1) ));

			//가장 큰 값을 찾아준다.
			String[] splitNum = subNum.toString().split("");

			Arrays.sort(splitNum,Collections.reverseOrder());

			//자릿수대로 가장 큰 값을 넣어준다.
			answer.append(splitNum[0]);

			//다시 문자열을 잘라준다.
			maxIndex = numberBuilder.indexOf(splitNum[0]);

			for ( int i = 0 ; i <= maxIndex; i++ ) {
				numberBuilder.setCharAt(i, '#');
			}

			// 구할 자리수의 범위도 점점 줄여나간다.
			size--;
		}

		return answer.toString();
	}

	public static String solution2(String number, int k) {
		
		StringBuilder answer = new StringBuilder();
		
		char[] numbers = number.toCharArray();
		
		// 가장 큰 값을 가지고있는 index를 기억한다.
		int index = 0 ;
		
		// 1차 loop 만들어야 하는 글자 수 만큼 처리한다.
		// i번째 자릿수의 범위를 결정하는대 i값이 쓰인다.
		for ( int i = 0 ; i < number.length()-k; i++ ) { 
			
			// 자리수 별로 max의 초기 값을 주기 위함이다.
			char max = '0';
			// i번째 자릿수가 올 수 있는 범위에서 최댓 값을 찾는다.
			for ( int j = index; j <= i+k; j++ ) {
				if( numbers[j] > max ) {
					max = numbers[j];
					index = j+1;
				}
			}
			// 범위에서 찾은 max 값을 answer에 apeend 해준다.
			answer.append(max);
		}
		return answer.toString();
	}
}//class

제출 결과

후기

엄청 많은 시간을 고민하였다..

 

처음에 구현한 solution메서드에서는 substring을 사용해서 처리대상 문자열을 계속 바꿔나갔다..

 

예를들면 [ 1924, 2 ] 로 주어진경우에 첫번째 자리수가 가능한 수는 [ 1,9 ] 이므로 1,9중에서 max값 9를찾고 max값을 가지고 있던 index다음부터 동일한 방법으로 찾아간다. 

 

1,9 -> max 9 찾고 9다음 index부터 처리

2,4 -> max 4 찾고 종료 .. 

 

max값을 찾았을때는 max값 이전의 값은 모두 '#'으로 변경해주어서 String.indexOf메서드 수행시 정상적으로 찾아 갈 수 있도록 하였다.

 

제출 결과는 8,9,10 테스트 케이스에대해서는 시간초과, 나머지는 통과하였다..

 

결국, 구글링을통해 해결방법을 학습하였다..

 

다른 사람이 구현한 코드를 분석한 결과, n번째의 글자를 표현 할 수 있는 범위를 어떻게 표현하는지가 핵심이였던 것 같다.

 

예를들면 [ "1231234" , 3 ] 으로 주어진 경우 return해야하는 글자는 총 4글자이다.

 

그러면이때 1번째 글자부터 ~ 7번째 글자가 선택 될 수 있는 범위를 정확하게 지정해 주는 것이다.

위의 예시는 이렇게 된다.

 

보면은 범위는 1씩 증가되고있고, 최초 선택 될 수 있는범위는 return 될 글자의 수 이다. 

 

[ 최초 선택 될 수 있는 범위가 = return 될 글자의 수 ] 가 되는 이유는.. 100개중에 6개를뽑아서 총 94개의 문자열을 만든다고하면 1번째 글자 뒤에는 적어도 93개의 숫자가 존재하기 때문이다...

 

결과적으로, https://geehye.github.io/programmers-greedy-02/# 블로그를 참조해서 해결하였다..

 

떠올릴 수 없으면 암기라도 할 수 있도록.. 알고리즘 문제를 더 많이 풀어봐야겠다..