코테/프로그래머스

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

imname1am 2023. 10. 20. 12:28
반응형

🔺 문제

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

🔺 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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();
    }
}
cs

 

🧩 해결 아이디어

• 그리디

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

 

 

 


🔺 다른 풀이들

- 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();
    }
}

 


💬 느낀 점

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

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

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

 

 

틀린 코드 확인하기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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(""00);
        
        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;
            }
        }
    }
}
cs

 

 

 

 

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

(참고)

 

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

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 이 문제를 보고 처음에 필자는 이렇게 생각했었다. '조합을 이용해서 숫자를 다 뽑은 다음에,

born2bedeveloper.tistory.com

 

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

문제 설명 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장

jhhj424.tistory.com

 

- 복습용으로 짱짱ㅠㅠ

 

 

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

https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 문제 문제 설명 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예

hyojun.tistory.com

 

반응형