[프로그래머스] 큰 수 만들기(Level 2)

📝문제 링크

프로그래머스 > 탐욕법 > 큰 수 만들기 문제보기

🔑문제 KeyPoint

HackerRank > Candies 문제처럼 앞뒤 숫자를 비교하여, 큰 수에 가중치를 주어서 접근해보았다.

// 앞 -> 뒤 비교하며 크면 가중치
for(int i=0; i < len-1; i++) {
	if(num[i] < num[i+1]){
		rank[i+1] = rank[i] + 1;
	}
}

// 뒤 -> 앞 비교하며 크면 가중치
for(int i=len-1; i >= 1; i--) {
	if(num[i] < num[i-1]){
		rank[i-1] = Math.max(rank[i]+1 , rank[i-1]);
	}
}

이렇게 풀면 제거해야 되는 수를 찾아내려면, 이중에서 몇개를 골라 순열을 만들어서 처리해야한다.

그래서 이렇게 접근을 하면 안된다고 생각을 했고, 다른 블로그들을 참조하여 힌트를 얻었다.

해당 문제는 위치가 단순히 숫자 제거만하고 숫자위치에 대한 변동이 없기 때문에,
0~k index사이에선 적어도 시작이 된다.
다음 숫자를 만들 수 있는 범위를 찾아가면서 가장 큰수를 선택하면 된다.

문제에 나온 예제2를 가지고 설명해보자.

이 문제를 이렇게 이해하기까지 꽤 많은 시간이 걸렸다.
이제 코딩을 해보자.

💻문제 풀이

public static String solution2(String number, int k){
	StringBuilder sb = new StringBuilder();		// 9,10 번 예외 케이스 때문에 StringBuilder 사용

	int len = number.length();
	int idx = 0; 		// 현재 위치

	// i, 숫자 len-k개를 뽑기위해 반복
	for(int i=0; i<len-k ; i++){
		char max = '0';
		// j, 시작은 idx ,
		// 범위는 k+i까지 ( k크기에다가 i는 뽑은 숫자만큼 늘려준다.)
		// 첫번째 숫자는 0~k index 사이에 존재함.
		for(int j=idx; j<=k+i; j++){
			// 현재 숫자가 가장 크다면, idx + 1 을 하여
			// 그 다음숫자부터 탐색하게 설정
			if(max < number.charAt(j)){
				max = number.charAt(j);
				idx = j+1;
			}
		}
		sb.append(max);
	}
	return sb.toString();
}

전체 소스보기(git)

[참조]

Greedy 프로그래머스 알고리즘 자바 ‘큰 수 만들기’ 문제풀이