[코테연습] 670. Maximum Swap

- 그리디 문제

 

https://leetcode.com/problems/maximum-swap/description/?envType=daily-question&envId=2024-10-17

 

- 문제분석

 

 주어진 정수 num의 자리 숫자들 중 두 자리 숫자를 한 번만 교환하여 만들 수 있는 가장 큰 수를 찾는 문제입니다.

힌트 1: 자리 수를 왼쪽에서부터 순차적으로 탐색

• 왼쪽부터 탐색: 큰 수를 만들기 위해서는 가장 높은 자리를 큰 숫자로 바꾸는 것이 유리합니다.
• 각 자리에서 그 뒤에 있는 숫자들 중 가장 큰 숫자를 찾아 교환하는 것이 핵심입니다.

힌트 2: 오른쪽에서 가장 큰 숫자를 기억하기

• 현재 자리에서 가장 큰 값을 찾으려면, 오른쪽에서 가장 큰 숫자를 기억하고 있으면 편리합니다.
• 오른쪽에 있는 숫자 중에 가장 큰 숫자가 있고, 그 숫자가 현재 자리 숫자보다 크면, 교환하여 최대 값을 얻을 수 있습니다.

힌트 3: 가장 첫 번째 교환만 고려

• 한 번의 교환만 가능하므로, 첫 번째로 교환이 가능한 자리에서 교환하고 탐색을 종료하면 됩니다.

예시:

• 입력: 2736
  • 가능한 교환 중 최대 값은 7236입니다. (2와 7을 교환)
• 입력: 9973
  • 이미 가장 큰 값이므로 교환할 필요가 없습니다. 결과는 9973입니다.

전략:

1. 왼쪽부터 탐색하면서 현재 숫자와 그 뒤에 있는 숫자 중 가장 큰 숫자를 찾습니다.
2. 교환이 가능하면 교환하고 종료합니다.

 

- 문제풀이

 

 

• 숫자를 리스트로 변환: num을 문자열로 변환한 뒤, 각 자릿수를 리스트로 변환합니다.
• 숫자의 마지막 위치 기록: 각 숫자가 리스트에서 마지막으로 등장하는 인덱스를 last 배열에 기록합니다. 예를 들어, 2736의 경우 last[2] = 0, last[7] = 1, last[3] = 2, last[6] = 3가 됩니다.
• 최대값 탐색 및 교환: 각 자리에서 자신보다 큰 숫자가 뒤에 있는지 확인합니다. 뒤에 큰 숫자가 있다면 해당 자리와 교환하고 즉시 결과를 반환합니다.
• 결과 반환: 교환이 없었다면 원래 숫자를 반환하고, 교환이 이루어졌다면 변경된 숫자를 반환합니다.

> java

 

class Solution {
    public int maximumSwap(int num) {
        char[] arr = String.valueOf(num).toCharArray();
        int n = arr.length;
        int[] last = new int[10]; // 각 숫자의 마지막 인덱스 기록

        for (int i = 0; i < n; i++) {
            last[arr[i] - '0'] = i;
        }
        for (int i = 0; i < n; i++) {
            int value = arr[i] - '0';
            for (int j = 9; j > value; j--) {
                if (last[j] > i) {
                    char temp = arr[i];
                    arr[i] = arr[last[j]];
                    arr[last[j]] = temp;
                    
                    return Integer.parseInt(new String(arr));
                }
            }

        }

        return num;
    }
}

 

 

> python

 

class Solution:
    def maximumSwap(self, num: int) -> int:
        num_list = list(map(int, str(num)))
        n = len(num_list)
        last = list(0 for _ in range(10))
        for i in range(n) :
            last[num_list[i]] = i

        for i in range(n) :
            value = num_list[i]
            for j in range(9, value, -1) :
                if last[j] > i :
                    temp = num_list[i]
                    num_list[i] = num_list[last[j]]
                    num_list[last[j]] = temp

                    return int("".join(map(str, num_list)))

        return num