[그리디] 큰 수 만들기 - Java코드 ★★★

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

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

https://hsin.hr/coci/archive/2011_2012/

Croatian Open Competition in Informatics

문제 출처이자 다양한 테스트케이스를 볼 수 있음  (4번의 테스트 다운후, kerk 폴더내 in, out 파일 참고)

 

문제 

 

나의 접근법 (오답)

number 문자열안에 가장 큰수인 9 ~ 0까지 순서대로 반복문을 돌면서,

해당수를 문자열 내에 큰수를 가장 먼저 만나는 부분에서 문자열을 잘라서,

가장 작은숫자부터 차례차례 제거하는 연산을 해서 반복해서 

답을 구하려했지만, 테스트케이스 3,4,5에서 걸렸다.

 

나의 풀이 (오답)

class Solution {
		 public  String solution(String number, int k) {		
		 StringBuilder str = new StringBuilder();
		 StringBuilder ans = new StringBuilder();
        	 loop:
		 for(char c='9'; c>='0';c--) {
			while(number.indexOf(c)!=-1 && k>0) {
				str.setLength(0);
				str.append(number.substring(0,number.indexOf(c)+1)); 
				number = number.substring(number.indexOf(c)+1);
				char ch='0';
				while(ch<c) {	
					while(str.indexOf(Character.toString(ch))!=-1 && k>0) {	
							str.deleteCharAt(str.indexOf(Character.toString(ch))); 
							k--;	
                    }
					ch++;
				}
				ans.append(str);
				if(k==0) {				 
					 break loop;
				}
			}
			
		 }
		ans.append(number);
		if(ans.charAt(0)=='0')
			return Integer.toString((Integer.parseInt(ans.toString())));
		return ans.substring(0,ans.length()-k);
	 }
}

 

문제는 

String number="6617423282157290684025607883097699259905250470744165128706131448395502185407310941966307933122347117";
int k=61;

이 케이스를 수행하고 나서 알게되었다.

답은 999999955285407310941966307933122347117 이지만
나는 999999955218547310941966307933122347117 이 나왔다.

올바른 설계

나는 큰수와 큰수 사이를 잘라서 0부터 작은수들을 먼저 제거하는 잘못된 설계를 했다,

정답은 작은수를 제거하는게 아니라, 차례대로 현재수보다 다음수가 크면 현재숫자를 제거하는 형태로 가고 있었다.

이걸 보자마자, Stack이 떠올랐다. 그래서 다시 만든 코드는 아래와 같다.

 

 

정답코드

    public String solution(String number, int k) {
        char[] result = new char[number.length() - k];
        Stack<Character> stack = new Stack<>();
        
        for (int i=0; i<number.length(); i++) {  // 하나씩 돌면서
            char c = number.charAt(i); 
            while (!stack.isEmpty() && stack.peek() < c && k-- > 0) { // top보다 큰값이면 pop()!
                stack.pop(); 
            }
            stack.push(c);
        }
        for (int i=0; i<result.length; i++) {
            result[i] = stack.get(i);
        }
        return new String(result);
    }

 

 

설계가 굉장히 Disgusting했다.

시간도둑..ㅜㅜ 

 

 

포인트

굳이 포인트를 집자면,

설계를 어떻게 하느냐, 사고력이 중요한 문제였고,

10번 테스트케이스 같은경우 문자열이 굉장히 길어 시간이 많이소요되므로,

반드시 문자열 연산은 String이나 StringBuffer보다 StringBuilder 객체를 사용해주는게 좋다.

시간복잡도를 최대로 낮추기 위해, 반복문을 최대한 적게 사용하자.