[Java] 자릿수 교환을 통한 최댓값 찾기

1. 문제

숫자 num 이 주어졌을 때, 최대 한 번의 자릿수 교환을 통해 최대의 숫자를 만들어 내려고 한다. 즉, 자릿수를 교환하지 않았을 때가 더 큰 숫자일 경우, 원래 숫자를 그대로 출력한다.

 

 

 

2. 입력 설명

• 10 <= num <= 1000000

 

 

 

3. 출력 설명

만들 수 있는 최대의 숫자를 반환

 

 

 

4. 매개변수 형식

num = 43824

 

 

 

5. 반환값 형식

83424

 

 

 

6. 입출력 예시 설명

0번째 인덱스의 숫자 '8' 과 2번째 인덱스의 숫자 '4'의 자릿수를 바꾸었을 때 가장 큰 수가 된다.

 

 

 

7. 힌트

그리디 알고리즘 사용

 

(1) 해결해야 할 조건들

• 자릿수가 낮아지면서 숫자가 커지는 위치가 있는지 확인한다.
  • 만약 숫자가 커지는 위치가 없다면 그 숫자가 가장 큰 숫자이므로 그대로 반환
  • ex) 987654321
• 숫자가 커지는 위치가 존재한다면 그 인덱스에 있는 값을 A 라고 가정할 때,
  
  • A보다 높은 자릿수에서 A보다 작은 숫자와 변경해야 하고
    
    • ex) 987658321 일 때, A는 8이고 바꿔줘야 할 수는 7이다.
  • A보다 낮은 자릿수에서 A보다 더 큰 수가 있는지 확인해야 한다.
    • ex) 987658093 일 때, A인 8 보다 더 큰 9가 뒤에 있기 때문에 9를 A로 선택해야 한다.
  • 발견한 A보다 더 큰 숫자이면서도, 더 낮은 자릿수에 있는 수를 A 로 선택해야 한다.
    • ex) 987658099 일 때, A 는 1의 자리에 있는 '9'가 A로 선택되어야 한다.

 

 

 

8. 코드 구현

class Solution {
    public int solution(int num) {

        // 각 자릿수에 접근해야 하기 때문에 int를 char[] 로 변환하여 접근한다.
        // Brute-force X
        // Greedy Algorithm O
        final char[] digits = String.valueOf(num).toCharArray();


        // index 1 부터 숫자가 커지는 위치가 있는 지 확인
        // 시간복잡도 : O(n)
        int increaseIdx = -1;
        for (int i = 1; i < digits.length; i++) {
            if (digits[increaseIdx] > digits[increaseIdx - 1]) {
                increaseIdx = i;
                break;
            }
        }


        // 일의 자리로 갈수록 작은 숫자를 가지고 있다면,
        // 지금이 가장 큰 숫자이므로 그대로 반환
        if (increaseIdx == -1) {
            return num;
        }


        // 위에서 찾은 숫자를 기준으로 더 큰 숫자가 있는지 찾는다.
        // 크기가 같더라도, 더 낮은 자릿수에 있는 수로 교체한다.
        // 즉, 크기가 크면서 가장 낮은 자릿수에 있는 숫자를 찾는다.
        // 시간 복잡도 : O(n)
        char maxVal = digits[increaseIdx];
        int maxIdx = increaseIdx;
        for (int i = increaseIdx; i < digits.length; i++) {
            if (digits[i] >= maxVal) {
                maxVal = digits[i];
                maxIdx = i;
            }
        }

        // 큰 자릿수부터 교체할 maxVal 보다 작은 숫자를 찾는다.
        // 더 작은 숫자를 발견하면 swap 하고 반환
        // 시간복잡도 : O(n)
        for (int i = 0; i < increaseIdx; i++) {
            if(digits[i] < maxVal) {
                digits[maxIdx] = digits[i];
                digits[i] = maxVal;
                return Integer.parseInt(String.valueOf(digits));
            }
        }

        return num;
    }
}