본문으로 건너뛰기

1432 - Max Difference You Can Get From Changing an Integer

정보

풀이 키워드​

스포주의

그리디


풀이 코드​

정보
  • 메모리: 40690 KB
  • 시간: 0 ms
class Solution {
    public int maxDiff(int num) {
        char[] numArr = String.valueOf(num).toCharArray();

        // mx: find the first none-9 digit & remap all targets to 9
        int target = -1;
        long mx = 0;
        for (int i = 0; i < numArr.length; ++i) {
            int n = numArr[i] - '0';
            if (target == -1 && n != 9) target = n;
            if (n == target) mx += 9;
            else mx += n;
            mx *= 10;
        }

        // mn: if the first digit is 1, find the first none-0 & none-1 digit & remap all
        //     else, the first digit is the taget. remap all targets to 1
        target = -1;
        long mn = 0;
        if (numArr[0] == '1') {
            mn = 10; // pre-set
            for (int i = 1; i < numArr.length; ++i) {
                int n = numArr[i] - '0';
                if (target == -1 && n != 0 && n != 1) target = n;
                if (n == target) mn += 0;
                else mn += n;
                mn *= 10;
            }
        } else {
            target = numArr[0] - '0';
            for (int i = 0; i < numArr.length; ++i) {
                int n = numArr[i] - '0';
                if (target == -1 && n != 1) target = n;
                if (n == target) mn += 1;
                else mn += n;
                mn *= 10;
            }
        }

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

풀이 해설​

2566 - Maximum Difference by Remapping a Digit의 후속 문제이다.

똑같이 오버플로우 부분에 대해서 유의하되,

이번엔 leading zero와 remap 후 0이 되면 안된다는 조건이 추가되므로

맨 앞자리가 1인지 1이 아닌지에 따라 분기해서 0 또는 1로 그리디하게 remap해주면 된다.

틀리기 쉬운 반례
111
답: 888

참고로, 상단처럼 맨 앞자리가 1이어도 무작정 이후에 target 잡아 0으로 remap 하면 안되는 반례가 있다.

이는 맨 앞자리가 1이어서 둘째 자리부터 target을 잡으면,

target이 1로 설정되어 mn이 100으로 remap되는 logic error가 발생할 수 있는 case이다.

if (numArr[0] == '1') {
    mn = 10; // pre-set
    for (int i = 1; i < numArr.length; ++i) {
        int n = numArr[i] - '0';
        if (target == -1 && n != 0 && n != 1) target = n;
        if (n == target) mn += 0;
        else mn += n;
        mn *= 10;
    }
} else {
    // ...
}

따라서 표시한 줄과 같이 맨 앞자리가 1이면, target 탐색에 1을 제외하는 추가적인 condition이 필요하다.


메모​

  • 복습 시 한번 슥 읽고 넘어가면 됨