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

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

프로그래머스

 

 

최대한 탐색을 적게 하기 위해, 탐색 범위를 좁히는 과정을 거친 후에, dfs 탐색을 했다.

근데 테스트케이스는 통과하지만 , 제출 시에 대부분의 케이스에서 런타임 에러가 발생했다.

 

아래가 기존에 작성한 코드이다. 

+) -> 바본가보다.. 굳이 dfs 탐색 안해도 될 문제였다. 첫번째 시작에서 탐색 범위 줄인 것처럼, 계속 탐색 범위 줄여가면서 탐색하면 된다...  ^^

import java.util.*;

class Solution {
    
    static int min_length;
    static int max_num = 0;
    public String solution(String number, int k) {
        
        min_length = number.length()-k;
        
        // number.length() - min_length 까지의 인덱스에 접근해서 가장 큰 수 구하기 (-> 탐색 범위 좁히기 위함)
        int index = number.length() - min_length;
        int max_value = 0;
        
        // 탐색 범위 좁히기 (앞자리 수가 가장 커야하니까 가장 큰 수 뽑기)
        for (int i = 0; i < index+1; i++){
            int first = number.charAt(i) - '0';
            max_value = Math.max(max_value, first);
        }
        
        // 앞자리 수가 가장 크면 dfs 탐색 시작하기
        for (int i = 0; i < index+1; i++){
            int first = number.charAt(i) - '0';
            if (first != max_value) continue;
            
            char arr[] = new char[min_length];
            arr[0] = number.charAt(i);
            
            boolean visited[] = new boolean[number.substring(i).length()];
            visited[0] = true; 
            dfs(number.substring(i), 1, 1, arr, visited);
        }
        
        return Integer.toString(max_num);
    }
    
    
    static public void dfs(String number, int depth, int index, char[] arr, boolean[] visited){
        
        if (depth == min_length){
            String return_str = "";
            for (char s: arr){
                return_str +=s;
            }
            
            max_num = Math.max(max_num, Integer.parseInt(return_str));
            return;
        }
        
        for (int i = index; i < number.length(); i++){
            if (!visited[i]){
                arr[depth] = number.charAt(i);
                visited[i] = true;
                dfs(number, depth+1, i+1, arr, visited);
                visited[i] = false;
            }
        }
        
    }
}

 

 

그래서 다른 풀이를 참고해서 다시 풀었다... ^^ 

이 마저도 인덱스 설정하는거 헷갈려서 인덱스 초과 에러 남. 수에서 규칙 찾는 문제가 난 아직도 어렵다.

 

해결책은 위에서 제시한 해결책과 동일하다. 

계속 인덱스 범위를 조절해나가며 제일 큰 수를 찾아 sb.append 해준다. 

• 탐색할 때 시작하는 인덱스 : 제일 처음은 0이고, 이 후에는 이전에 선택된 인덱스 + 1
• 탐색할 때 마지막 인덱스 : i+k (코드 참고)

그리고, 풀었음에도 계속 10번에서 시간초과가 났다. 

원래 코드에서는 숫자 크기를 비교할 때 charAt(j) -'0' 으로 해서 int로 변환해준 후에 수 비교를 했는데, 연산횟수가 더 늘어나다보니 초과가 난 것이다. (사소한 연산이라고 생각했는데, 시간초과 나는 테스트케이스를 만들다니,,,)

 

=> 해서 char 형으로 서로 크기 비교를 하도록 했다. 연산 횟수도 더 줄어들었고 테케를 다 통과할 수 있었다!

오늘의 교훈 : 사소한 연산이라도 줄이자... ! 

 

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

 

 

Reference

https://jhhj424.tistory.com/32

[알고리즘] 프로그래머스 큰 수 만들기(Level 2) [자바/JAVA] 풀이- 개발하는 지토