본문으로 건너뛰기

2566 - Maximum Difference by Remapping a Digit

info

풀이 키워드​

스포주의

그리디


풀이 코드​

info
  • 메모리: 41240 KB
  • 시간: 0 ms
class Solution {
    public int minMaxDifference(int num) {
        // greedy
        // mx, mn should be long type in case of num=100000000
        // the first none-9 / none-0 digit is the target
        // mx: remap all targets to 9
        String numStr = String.valueOf(num);
        char[] numArr = numStr.toCharArray();

        int targetDigit = -1;
        long mx = 0;
        for (int i = 0; i < numArr.length; ++i) {
            int n = numArr[i] - '0';
            if (targetDigit == -1 && n != 9) targetDigit = n;
            if (n == targetDigit) mx += 9;
            else mx += n;
            mx *= 10;
        }

        // mn: remap all targets to 0
        targetDigit = -1;
        long mn = 0;
        for (int i = 0; i < numArr.length; ++i) {
            int n = numArr[i] - '0';
            if (targetDigit == -1 && n != 0) targetDigit = n;
            if (n == targetDigit) mn += 0;
            else mn += n;
            mn *= 10;
        }

        return (int)(mx/10 - mn/10);
    }
}

풀이 해설​

수가 주어지면 임의의 한 숫자를 정해서 다른 숫자로 일괄 변경이 가능한데

이러한 규칙을 이용해서 만들어지는 수 중 가능한 최대값, 최소값을 구한 후 서로의 차를 구하는 문제이다.

당연히 높은 자리의 숫자를 9또는 0으로 바꾸는게 유리한 그리디 유형임을 알 수 있다.


물론 이미 맨 앞자리가 9일 수 있으므로 (0일 순 없겠군...)

num을 배열화한뒤 각 숫자를 스캔해서, 가장 먼저 나오는 '9/0이 아닌 숫자'를 찾아

이를 target으로 지정하고, 해당 시점부터 target은 다 9 또는 0으로 변환한다.


caution

💥 함정 주의​

for (int i = 0; i < numArr.length; ++i) {
    // ...
    mx *= 10;
}

for문의 마지막 줄 수행이 *= 10이기 때문에,

for문이 끝난 직후 mx는 원래 주어진 수보다 한 자리 더 늘어나있게 된다.
(mn은 늘어나진 않겠지만 그래도 일의자리를 버려야 하는건 마찬가지)

return (int)(mx/10 - mn/10);

그래서 각자 10씩 나눠서 일의자리 떼고 반환하지만, 여기서 실수하기 쉬운 점이 있다.

num의 범위는 [1, 108][1,\,10^8]이기 때문에, num이 100000000100000000으로 주어지면

mn은 몰라도 mx는 마지막 *= 10 연산때문에 오버플로우된다.
1억의 맨 앞자리를 9로 바꿔서 9억인데 여기에 10이 더 곱해지면 90억... int에 넣으면 오버플로우 퍼퍼펑

따라서 안전하게 long으로 다루자.


메모​

  • 괜찮은 easy 난이도 문제
  • 10810^8 부턴 기본적으로 오버플로우 경계해야할 듯