[프로그래머스 : 레벨2] 큰 수 만들기 :Stack (Java)

위문제는 내가 문제를 테스트 케이스로는 정답을 냈지만 나머지는 런타임 에러가 났다.

그럴법도 한게 나는 완전 탐색으로 모든 조합을 구한후에 정렬을해서 가장 큰수를 뽑았기 때문이다.

 

내가 간과한 부분은 문제의 제한조건에서 

number는 1자리 이상, 1,000,000자리 이하인 숫자

라는것을 간과했다.

 

완전탐색은 모두 탐색하는것이기에 시간이 엄청 오래걸리는데 저렇게 큰수로 완전탐색을 하게 된다면 내가한 방식으로

소스를 풀게되면 하루종일 컴파일이 될것이다.

 

그래서 어쩔수없이 또 답지를 보게 되었다.

 

문제를 한번 보자.

 

문제 설명

 

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

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 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"

 

위 문제를 보고는 처음에 정려를 해서 가장 큰수를 뽑아오는것인줄 알았다.

그래서 1231234 인 경우에는 4332가 답이되어야 하는것이 아닌가? 했는데 알고보니 이것은 문자열의 순서를 그대로

지키는것이다.

 

그래서 이건 문자열의 각각의 문자에 접근을 해서 넘어갈때마다 각각의 수중 큰수만 선택하는 방식으로 하면 된다.

 

그래서 내가 보게된 소스중 아래의 소스가 제일 가독성도 있었고 시간도 빨랐다.

 

소스는 아래와 같다.

 

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		PreTest p = new PreTest();
		int k = 2;
		String name1 = "1924";
		String name2 = "1231234";
		System.out.println(p.solution(name1,k));
		
	}
	
    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); //1924에 직접 접근
            while (!stack.isEmpty() && stack.peek() < c && k-- > 0) { //stack이 비어있지 않고 스택에 있는게 현재위치의 수보다 작고 k-- 한게 0보다 크면
                stack.pop(); //맨위에를 뽑는다.
            }
            //위의 상황이 아니라면 stack에 넣는다.
            stack.push(c);
        }
        for (int i=0; i<result.length; i++) {
            result[i] = stack.get(i);
        }
        return new String(result);
    }

"1924"라는 수를 받았다고 치면

1, 9, 2, 4

이렇게 각각 접근해서 처음에 스택이 비어있다면 값을 집어 넣고

그 이후부턴 값을 비교해 값이 더크다면 stack에서 빼고 수를 집어 넣는 방식으로 했다.

그리고 k의 수도 pop() 시킬때마다 줄어들게해서 3자리수만 남았을 시점엔 해당 수들은 그냥 push()만 하게 한다.

 

(Stack에 관해서 잘 모르시는 분들은 아래링크를 통해 보고오시면 소스가 더 이해하기 수월할것이다.)

https://wpioneer.tistory.com/111

[Java] Stack 클래스 사용방법

 

그리고 k의 수도 pop() 시킬때마다 줄어들게해서 3자리수만 남았을 시점엔 해당 수들은 그냥 push()만 하게 한다.

 

느낀점

1. 제한조건에서 숫자가 몇까지인지를 잘 확인하자.

2. 탐욕알고리즘은 항상 매순간 선택을 하는것이니 매순간순간 선택을 하는 알고리즘을 짜도록하자.

3. 이 세상에 똑똑한사람은 정말 많다.