프로그래머스[Java] - 큰 수 만들기

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

코딩테스트 연습 - 큰 수 만들기 | 프로그래머스

 

코드

class Solution {
	public static String solution(String number, int k) {
		StringBuilder sb = new StringBuilder(number);
		int delCount = 0;
		int index = 1;
		int i = 0;
		
		while(delCount != k) {
			
			// 4 1 7 7 ... <- 1 7 비교해서 뒤에 숫자가 더 크면 앞 숫자 제거
			// 제거했으니 앞 index(4, 7)를 비교하기 위해 index --, 
			// 제거한 delCount ++;
			if(index >= 1 && sb.charAt(index-1) < sb.charAt(index)) {
				sb.deleteCharAt(index-1);
				index --;
				delCount ++;
			}
			else {
				// index가 가장 끝값일때
				if(index == sb.length() - 1 && sb.charAt(index) <= sb.charAt(index-1)) {
					sb.deleteCharAt(index);
					delCount ++;
					index --;
				}
				else {
					index ++;
				}
			}
		}
		
		return sb.toString();
	}
}

 

풀이

문제를 보고 생각하다가 마땅히 떠오르는 방법이 없어서 블로그를 참고했다 ..

생각보다 꽤나 복잡하고, 다른 풀이들을 보면 스택을 이용해 푼 풀이가 많았다.

 

일단 위풀이는,, 입력받은 문자열 변수 number을 삭제하기 용이한 StringBuilder로 변환해서 푼다.

가장 큰 숫자를 만들어야 하므로 가장 앞에있는 숫자는 가장 큰 숫자가 나와야 하고, 비교하면서삭제하는 식으로 푼다. 삭제한 갯수와 k가 같을때 while문을 종료한다.

 

number = "41772528 " 와 같을때

index = 1일때... index-1(4) 와 index(1)을 비교한다. => 4가 더크므로 index를 증가시켜준다.

index = 2일때... index-1(1) 와 index(7)을 비교한다. => 7이 더 크므로 index-1(1)을 삭제하고, delCount를 증가시켜준다. 그 전에 비교한 4와 비교하기위해 index를 감소시킨다.

index = 1일때... index-1(4)와 index(7)을 비교한다. => 7이 더 크므로 index-1(4)을 삭제하고, delCount를 증가시켜준다. index를 감소시킨다.

index = 0일때... index를 증가시켜준다.

 

위와 같은 조건으로 반복되는데,, 주의할점은 같은숫자가 연속적으로 나타난 숫자이다.

number = "1000000" , k = 3

위와 같은 숫자는 index가 계속 증가해도 숫자를 삭제하지않는다.

따라서 index의 값이 number의 길이와 같고, index-1 값이 index 값보다 크거나 같을때 index를 삭제한다.