[AlphaGo Study] [Programmers] [JAVA] 큰 수 만들기

 

문제 설명

 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다.

 number에서 k개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 사항

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

입출력 예 설명

#예제

숫자 1924에서 두 수(k = 2)를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 "94"입니다.

 

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

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

---

StringBuilder

   § String 객체와 String 객체를 더하는 행위는 메모리 할당과 메모리 해제를 발생시키며, 더하는 연산이 많아진다면 성능적으로 좋지않다.

   § 이를 해결하기 위해 사용하는 것이 StringBuilder이다.

   § String과 문자열을 더할 때 새로운 객체를 생성하는 것이 아니라, 기존의 데이터에 더하는 방식을 사용하기 때문에 속도가 빠르며 상대적으로 부하가 적다.

   § 출력을 할 때에는 toString()을 사용한다.

charAt(int index)

   § 입력 받은 index번째 문자를 반환한다.

   § ex)

String str = "Hello Hammieunseo~!"
str.charAt(7);

에서 결과는 a가 나온다. index는 0부터 시작한다.

문제를 풀기 전 THINK

   § k개를 지우는 것 = number의 length - k개를 선택하는 것.

   § i 번째의 숫자에서 선택할 수 있는 숫자는 i + k 까지.

     ☞ 예를 들어, k = 3이고 number = "1231234"인 경우에, i = 0 에서 선택할 수 있는 숫자는 0 + 3인 3번째 숫자까지.

          answer의 길이가 length - k = 7 - 3 = 4 이므로, 0번째 숫자에서 하나만 선택하고 다 버릴 경우에,

          4 ~ 6의 범위 내에서 숫자를 선택해야 하기 때문.

     ☞ i 시점에서 k개를 다 버려도 answer의 길이(여기에선 4)에 영향이 없는 범위까지 선택.

   § 범위 내에서 숫자를 선택하고 나면, 그 다음의 index에서부터 다시 수를 찾기 시작.

나의 Solution

public class MakeBigNumber {
	public String solution(String number, int k) {
        
        StringBuilder sb = new StringBuilder();
        int n_len = number.length();
        
        // 선택하는 수의 길이 ex) number = 1231234, k = 3 -> select_num = 7 - 3 = 4
        int select_num = n_len - k;
        char maxNum; // 선택한 최대의 숫자 값
        int start = 0; // number의 시작 index
        int end = 0; // number의 끝 index
        
        // 선택될 수 있는 숫자의 길이만큼 for
        for(int i = 0; i < select_num; i++) {
        	maxNum = number.charAt(start);
        	
        	// 선택 index보다 큰 숫자가 나오면 해당 숫자를 maxNum에 저장하고,
        	// 그 index를 end에 저장
        	for(int j = start; j <= (i + k); j++) {
        		if(maxNum < number.charAt(j)) {
        			maxNum = number.charAt(j);
        			end = j;
        		} // if end
        	} // for end
        	
        	sb.append(maxNum);

          	// maxNum에 저장하고 나면 다음 index로 가기
        	start = end + 1;

          	// end에 start 값을 넣어 index를 옮겨줌
         	end = start;
        	
        } // for end
        return sb.toString();
    }
}

Comment...

이거 정말 어려웠다...어려워서 코멘트를 쓸 수 밖에 없어....딱히 쓸 말은 없지만..