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

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

프로그래머스

---

- 문제 풀이

 

1. 필요한 변수 초기화

StringBuilder answer = new StringBuilder(); // 결과를 저장할 문자열 빌더
int length = number.length() - k; // 최종적으로 남아야 할 숫자의 길이
int index = 0; // 탐색 시작 인덱스

 

• StringBuilder 객체인 answer를 생성하여 결과 문자열을 저장합니다. StringBuilder를 사용하면 문자열을 효율적으로 수정할 수 있습니다.
• length는 최종적으로 남아야 할 숫자의 길이를 계산한 것으로, 이는 number.length() - k로 구합니다. 이 값을 통해 선택해야 할 자리 수를 결정합니다.
• index는 탐색을 시작할 인덱스를 나타내며, 처음에는 0으로 초기화합니다.

 

 

 

2. Greedy 알고리즘을 사용하여 가장 큰 숫자를 선택

for (int i = 0; i < length; i++) {
    char max = '0'; // 가장 큰 숫자를 찾기 위한 초기값
    // 2. 선택할 숫자의 범위를 제한 (현재 인덱스부터 k+i까지)
    for (int j = index; j <= k + i; j++) {
        if (number.charAt(j) > max) {
            max = number.charAt(j);
            index = j + 1; // 선택된 숫자 이후부터 다음 탐색 시작
        }
    }
    answer.append(max); // 가장 큰 숫자를 결과에 추가
}

 

• for 루프는 length만큼 반복되며, 남아야 할 숫자의 길이만큼 큰 숫자를 선택합니다.
• max 변수는 현재 탐색 구간에서 가장 큰 숫자를 저장하는 변수로, 초기값은 '0'으로 설정합니다.
• 내부 for 루프에서 j는 현재 인덱스 index부터 k + i까지 탐색합니다. 여기서 k + i는 탐색 범위를 설정하는 기준으로, 이 범위 내에서 가장 큰 숫자를 찾아야 합니다.
• number.charAt(j)가 현재 max보다 크면 max를 갱신하고, index를 j + 1로 업데이트하여 다음 탐색 범위를 설정합니다.

 

 

 

 

 

3. 가장 큰 숫자를 결과 문자열에 추가 및 최종 결과 반환

 

            answer.append(max);
        }
        return answer.toString();
    }
}

StringBuilder에 저장된 결과 문자열을 toString() 메서드를 사용하여 반환합니다.

 

 

 

 

---

예시 실행

 

예제 1: "1924", k = 2

• 목표: 2개의 숫자를 제거했을 때 가장 큰 수를 구한다.
• 최종적으로 남아야 할 길이: 4 - 2 = 2 (즉, 2자리 숫자가 되어야 한다.)

과정:

1. 첫 번째 자리 수 선택 (i = 0):
   • 탐색 범위: index = 0부터 k + i = 2까지 (192에서 가장 큰 수를 찾음).
   • max = '0'으로 초기화하고 순차적으로 비교한다.
     • '1' > '0'이므로 max = '1'.
     • '9' > '1'이므로 max = '9'.
     • '2' < '9'이므로 max는 그대로 '9'.
   • 가장 큰 숫자는 '9'이므로 결과 문자열에 추가하고, index를 2 + 1 = 3으로 설정한다.
2. 두 번째 자리 수 선택 (i = 1):
   • 탐색 범위: index = 3부터 k + i = 3까지 (4에서 가장 큰 수를 찾음).
   • 유일한 숫자는 '4'이므로 바로 추가.

• 최종 결과: "94"

 

---

 

- 정답 코드

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder(); // 결과를 저장할 문자열 빌더
        int length = number.length() - k; // 최종적으로 남아야할 문자열 길이
        int index = 0; // 탐색 시작 인덱스

        for(int i = 0; i < length; i++) {
            char max = '0'; // 가장 큰 숫자를 찾기 위한 초기값
            // 2. 선택할 숫자의 범위를 제한 (현재 인덱스부터 k+i까지)
            for(int j = index; j <= k + i; j++) {
                if(number.charAt(j) > max){
                    max = number.charAt(j);
                    // max로 지정된 인덱스의 다음 인덱스로
                    index = j + 1;
                }
            }
            answer.append(max);
        }
        return answer.toString();
    }
}