[알고리즘] Greedy - 큰 수 만들기

프로그래머스 Lv2 - 큰 수 만들기

처음에는 ArrayList를 이용해서 배열을 넣고, 완전 탐색을 이용하였다

하지만 시간 초과 + 정답 오류 가 계속 반복되어 나타나는 걸 보고 구글링을 시도하였다.....(최후의 수단)

제한 조건을 자세히 보면 number의 값이 1,000,000자리까지 나올 수 있는데,

완전 탐색을 이용하면 최악의 경우에 1,000,000C999,999의 경우의 수가 나올 수 있기 때문에 절대 사용 금지이다

 

풀이 방법은 다음과 같다

class Solution {
    public String solution(String number, int k) {
    	StringBuilder sb = new StringBuilder();
    
    	int idx = 0;
    	int max = 0;
    	for(int i=0; i<number.length()-k; i++) {	
    		max = 0;
    		for(int j=idx; j<=i+k; j++) {
    			if(max < number.charAt(j)-'0') {
    				max = number.charAt(j)-'0';
    				idx = j+1;
    			}
    		}
    		sb.append(max);
    	}
    	return sb.toString();
    }
}

우선 시간 절약을 위해 StringBuilder를 이용하여 그때그때 큰 수를 추가해 준다

문제를 보면 k개의 숫자를 제거하여 가장 큰 수를 만들어야 하는데, 역으로 생각하면 number-k개의 큰 숫자를 찾아내는 문제다

먼저 첫 번째 반복문에서 우리가 찾아야 하는 숫자의 개수(n-k번)만큼 돌도록 하였다

첫번째 반복문을 한 바퀴 돌때마다 max값(idx)을 찾아내고, 그 다음 반복시 max값의 다음(idx+1)부터 i+k까지 최대값을 찾는 것이다

number의 크기가 8, k가 3이라고 가정했을 경우

어차피 i는 (n-k-1)까지니까 j의 값은 최대 n-k-1+k = n-1까지 돌게 된다! (범위를 벗어나는 일은 없음)

완전 탐색 보다 그때그때 최선의 선택을 하는 greedy 알고리즘이 훨씬 효율적이기 때문에 이 방법을 이용하였다풀이를 보니 Stack을 이용하는 사람도 보았는데,,, 천재같았다다음에 다시 Stack으로 도전해봐야겠다

 

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