[프로그래머스] 큰 수 만들기 for JAVA _ 그리디 알고리즘

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

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

 

 

 

 

문제

 

 

 

---

안봐도 되는 실패기

 

 

위의 문제 알고리즘은

 

왼쪽 숫자부터 그 옆 숫자와 비교하여 오른쪽 숫자가 더 크면 왼쪽 숫자를 지우는 방식을 사용하였다.

 

 

그러니까 4177252841 에서 4, 1을 비교하면 4 < 1 이므로 넘어가고

 

1 < 7 이므로 1을 삭제한다.

 

그러면 477252841이 되고 4 < 7 이므로 4를 삭제하여 77252841이 되고

 

2 < 5 이므로 2를 삭제하여 7752841, 2 < 8 이므로 775841 이 return 되는 것이다.

 

 

그래..알고리즘은 이렇게 짰고 구현을 할 때 2중 for문으로 k번 만큼 돌게, 왼쪽부터 훑어서 왼 < 오 가 되면

 

substring으로 잘라서 저장하는 방식을 사용하였는데

 

시간 초과가 어마어마하게 떴다^^ + 테스트 12는 실패;

 

당연함 number가 최대 1,000,000자리인데 이걸 다 훑어야함..

 

 

 

망한 코드

    
class Solution {
    public String solution(String number, int k) {
        String answer = "";
        
        for(int i = 0; i < k; i++){
	            for(int j = 0; j < number.length()-1; j++){
                    if(number.charAt(j) < number.charAt(j+1)){
	                    number = number.substring(0, j) + number.substring(j+1);
	                    break;           
	                } else if(j == number.length()-1){
	                    number = number.substring(0, j);
	                    break;
	                }
	                else continue;
                    
	            }
	        }
	        
	        answer = number;
	        return answer;
        
    }
}

 

 

구데기 성능

 

 

그래서 남의꺼 참고하기로 했다.

 

 

---

https://jhhj424.tistory.com/32

이분꺼 참고했다.

 

 

내가 생각한 것처럼 비교해서 훑지 말고 큰 수를 뽑아낸다는 생각을 해야한다.

 

 

예를 들어 4177252841 중에 4개를 뺀 6자리 수 가 들어가야하므로 4177252만 살펴보자

 

여기서 가장 큰 수를 찾는다. index = 2인 7이 가장 큰 수가 된다. 얘를 더한다.

 

 

index = 2 였으므로 다음 인덱스인 3번째부터 또 큰 수를 찾는다. index = 3인 7이 가장 큰 수가 된다.

 

7을 더한다. 이런식으로 푸셨다~~

 

 

 

코드

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

 

 

j <= k+i 로 하면 앞쪽만 훑다가 number의 마지막꺼까지 훑을 수 있다....

 

number.charAt을 사용해 char이 된 수를 - '0'을 해줌으로써 숫자로 형 변환을 해서 stringbuilder인 answer에 append 하고

 

마지막에는 string 값으로 return 해야하므로 .toString()을 사용해줬다.

 

 

성능

 

 

테스트 10은 아무래도 모두 같은 숫자를 넣어서 다 훑어야하는 테스트케이스가 아닐까..... 시간 복잡도가 엉망이다

 

 

---

또 보는 남의 코드

 

 

 

 

 

스택을 이용해 내가 사용하려고 했던 것처럼

 

뒤에 들어오는 숫자가 바로 전 숫자보다 큰지 확인해서 크면 전 숫자를 pop 시키고 자신은 push로 넣어주는 방식을 반복한다.

 

 

진짜 대박!!!!!!!!!

 

 

 

 

 

 

아~ 얘도 왼오 비교하고 오른쪽거가 더 크면 왼을 delete 해준다. 그렇구나....

 

그리고 k != 0 일 때는 숫자가 내림차순일 경우이므로 맨 오른쪽 숫자를 없애준다.