[프로그래머스] 탐욕법(Greedy) > 큰 수 만들기 (java)

탐욕법(그리디 알고리즘, Greedy Algorithm)

그리디 알고리즘(욕심쟁이 알고리즘)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법이다.

 

그리디 알고리즘에 관한 좀더 자세한 내용은 아래를 확인하자.

그리디 알고리즘 - 나무위키

 

우선, 나의 마지막 코드를 보기 전에 문제를 맞추기 위한 여정을 말해보려한다.

같이 헛다리 장인의 헛다리를 하나씩 살펴 보도록 하자.

 

나의 설계

1. 처음 나의 설계는 이러했다.

총 k개의 숫자를 제거해서 가장 큰 수를 만들어야 하니,

부분 문제로 1개의 숫자를 제거했을 때 만들 수 있는 가장 큰 수이면,

이를 k번 반복 했을 때, k개의 숫자를 제거한 가장 큰 수 일 것이다.

 

그래서 매번 1개의 숫자를 제거했을 때 가장 큰 수를 찾기 위해

모든 숫자를 한 번씩 제거해서 최대 값을 찾았다.

그러고 나서 숫자를 비교하기 위해 String -> int로 변경하였다.

 

문제점 )

- 우선 테스트 케이스 11, 12번은 통과를 하였지만 나머지는 런타임 에러가 발생했다.

number가 1부터 1,000,000까지 인줄 알았는데, 1자리 이상 1,000,000자리 이하라고한다....

java의 int 범위는 -2,147,483,648~2,147,483,647로 9자리만 넘어도 런타임 에러가 발생했던 것이다...

 

2. 그래서 int로 변경하지 않고, String.comparaTo(String)을 이용하여 비교를 하였다.

그랬더니, 1~5, 11, 12번은 통과 하였지만 나머지는 시간 초과로 실패하였다.

 

문제점 )

- 1개의 숫자를 제거하기위해 number를 완전탐색하고 있고, 이를 k번 반복하니 비용이 많이 든다.

1개의 숫자를 제거하기위한 비용을 줄이기 위한 방법을 생각 해보자!

 

3. 그래서 생각해낸 방법이

n개의 숫자 중 1개의 숫자를 제거했을 때 값에 가장 많은 영향을 주는 곳이 자릿수가 높은 곳을 변경하는 것이다.

그래서 자릿수가 가장 높은 곳(h)의 값과 그 오른쪽(h-1)의 값을 비교한다.

여기서 자릿수가 가장 높은 곳을 왼쪽이라고 하겠다.

(왼쪽 값 < 오른쪽 값) 이면 왼쪽 값을 제거

(왼쪽 값 >= 오른쪽 값) 이면 왼쪽 값은 유지되고 한 칸 오른쪽으로 이동해서 다시 값을 비교한다.

즉, h의 값 >= (h-1)의 값 이면 h-1 과 h-2 의 값을 비교한다.

만약 이를 끝까지 반복했다면

남은 값들은 내림차순으로 정렬된 상태이다.

그래서 제거해야 할 수가 남았다면 남은 수만큼 뒤에서부터 잘라주면된다.

 

그랬더니, 이제 10번만 시간초과를 하고 나머지는 다 통과이다.(얼마 남지 않았다!)

 

4. 시간 초과가 났다는 것은 최적화가 되지 않았다는 의미일 수도 있다.

String이 속도에 연관이 있을 것 같았다. 왜냐면 String.substring()을 많이 사용하기 때문이다.

String의 속도를 좀 더 빠르게 하기위해서 StringBuffer와 StringBuilder를 이용한다고 한다.

그래서 나는 StringBuilder를 이용해서 String.substring()대신 StringBuilder.deleteCharAt()을 이용하였다.

 

그리고 찾아낸 max 값을 지역 변수에 저장하고 반환하는 과정을 제거해 주었다.

이 과정에서도 어느정도 속도를 저하시킨다고 하여서..

 

그랬더니 결국 10번까지 통과를 하게되었다.

 

5. 하지만 10번을 통과하는데 걸린 시간이 4000ms(4초)이다...

문제를 다 풀었으니 다른사람의 풀이를 볼 수 있기에 다른 풀이들도 살펴 보았다.

String은 Charater의 배열이다.

StringBuilder가 아닌 Character배열을 이용해서 푼 분의 코드를 돌려보니 10번에서 100ms밖에 안 걸리더라...

물론 그 분은 Stack을 이용해서 높은 자릿수의 값들을 유지하면서 문제를 풀어갔지만,

어느정도 흐름은 나의 알고리즘과 비슷하게 느껴진다.

 

오늘도 기본에 충실하지 못했던 헛다리 장인은 또 한번 벽을 느끼게 된다...

 

이상 부끄럽지만 나의 코드이다!

나의 코드

class Solution {
	public String solution(String number, int k) {
        String answer = findMax(number, k);
        return answer;
    }
    
	// 가장 큰 수 만들기
	private String findMax(String number, int k) {
		boolean isDescOrder = false;
		StringBuilder strBuilder = new StringBuilder(number);
		
		for(int i = 0; i < k; i++) {
			if(isDescOrder) {
				return number.substring(0, k-i+1);
			}
			int j = 0;
			int size = strBuilder.length() - 1;
			for(; j < size; j++) {
				char left = strBuilder.charAt(j);
				char right = strBuilder.charAt(j+1);
				if(left < right) {
					strBuilder.deleteCharAt(j);
					break;
				}
			}
			if(j == size) {
				strBuilder.deleteCharAt(size);
				isDescOrder = true;
			}
		}
		return strBuilder.toString();
	}
}

 

이상 프로그래머스 탐욕법 큰 수 만들기를 마치겠다!

 

다음은 해당 문제를 풀 수 있는 프로그래머스 주소이다.

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