[프로그래머스/Lv. 2] 큰 수 만들기 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

class Solution {
    public String solution(String number, int k) {
       StringBuilder sb = new StringBuilder();
        
        int idx = 0;    // 탐색해야 하는 문자의 시작 인덱스
        int max = 0;
        
        for(int i = 0 ; i < number.length() - k ; i++) {
            max = 0;
            
            for(int j = idx ; j <= i + k ; j++) {
                if(max < number.charAt(j) - '0') {
                    max = number.charAt(j) - '0';
                    idx = j + 1;    // 가장 큰 수의 다음 인덱스 넣기
                }
            }
            sb.append(max);
        }
        
        return sb.toString();
    }
}

 

🧩 해결 아이디어

• 그리디

- 보장되어야 할 자릿수를 남겨두고, 나머지 부분에서 최댓값 찾아 숫자 이어붙임

 

 

 

---

🔺 다른 풀이들

- deleteCharAt() 활용하신 분들도 계신다...

class Solution {
    public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder(number);
        for (int i = 0; i+1 < sb.length() && k>0; i++) {
            if(sb.charAt(i) < sb.charAt(i+1)) {
                sb.deleteCharAt(i);
                i=-1;
                k--;
            }
        }
        if(k!=0)
            sb.delete(sb.length()-k, sb.length());
        return sb.toString();
    }
}

 

---

💬 느낀 점

사실 틀려서 다른 분 풀이를 보고 작성했다.

백트래킹으로 해봤는데 시간초과가 발생했다.

(아무래도 크기가 최대 백만이다 보니..)

 

 

틀린 코드 확인하기

import java.util.*;
 
class Solution {
    static String number;
    static int k;
    
    static boolean[] visited;
    static int max = Integer.MIN_VALUE;
    
    public String solution(String number, int k) {
        this.number = number;
        this.k = k;
        
        visited = new boolean[number.length()];
        
        back("", 0, 0);
        
        return Integer.toString(max);
    }
    
    private static void back(String str, int sIdx, int depth) {
        if(depth == number.length() -k) {
            max = Math.max(max, Integer.parseInt(str));
            return;
        }
        
        for(int i = sIdx ; i < number.length() ; i++) {
            if(!visited[i]) {
                visited[i] = true;
                back(str + number.substring(i, i+1), i + 1, depth + 1);
                visited[i] = false;
            }
        }
    }
}

 

 

 

 

1회독	2회독	3회독	4회독	5회독
V	240213

---

(참고)

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

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

 

- 복습용으로 짱짱ㅠㅠ

 

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