[Leetcode]670. Maximum Swaps

문제 요약

• 알고리즘 분류:  구현, 브루드 포스, 그리디
• 난이도: Medium
• 문제내용:
  • 숫자 num이 주어지고 두개 숫자 변경 해서 최대 값을 구하여라
• 사이트 주소: https://leetcode.com/problems/maximum-swap/

문제풀이

이번 문제는 숫자 2개만 바꿔서 그 중 최대 값만 반환 하기 때문에 어렵지 않다고 생각하낟. 그래서 아래 처럼 구현만 된다.

1. 숫자를 배열 또는 리스트로 만든다. 그리고 num값을 최대값으로 지정 한다.
2. 이중 for문 돌려서 i는 0 ~ 배열 크기 -1, j는 i + 1 ~ 배열 크기 만큼 돌린다.
3. i, j 바꾸고난뒤 숫자로 변환 한뒤 이전 최대 값과 비교하여 그중 큰 값으로 저장 한다.

 위 처럼 구현하면 시간 복잡도는 num의 자리수를 N이라고 볼면 O(N^2)만큼 나온다. 근데 숫자가 10^8승이 최대라서  의미는 없다고 보면 된다. 위 방법 말고 그리디 방법 있는데 그 방법 추후에 다시 작성 하겠다.

 

Code

Python

class Solution:
    def maximumSwap(self, num: int) -> int:
        array_number = list(map(int, list(str(num))))  # 숫자 배열로 변환
        max_num = num  # 초기 최대값을 현재 숫자로 설정
        size = len(array_number)

        for i in range(size - 1):
            for j in range(i + 1, size):
                # i, j 바꾸기
                array_number[i], array_number[j] = array_number[j], array_number[i]

                # 숫자를 다시 정수로 변환하여 최대값과 비교 후 갱신
                max_num = max(max_num, int(''.join(map(str, array_number))))

                # 원위치
                array_number[i], array_number[j] = array_number[j], array_number[i]

        return max_num

Java

class Solution {
    public int maximumSwap(int num) {
    int maxNum = num;

    String numStr = String.valueOf(num);
    int size = numStr.length();

    int[] nums = new int[size];

    for (int i = 0; i < size; i++) {
      nums[i] = numStr.charAt(i) - '0';
    }

    for (int i = 0; i < size - 1; i++) {
      for (int j = i + 1; j < size; j++) {

        // swap
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;

        // 숫자를 다시 정수로 변환하여 최대값과 비교 후 갱신
        maxNum = Math.max(maxNum, arrayToInteger(nums));

        // 다시 원위치
        temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;

      }
    }


    return maxNum;
  }

  // 배열을 숫자로 변환
  public int arrayToInteger(int[] array){
    StringBuilder sb = new StringBuilder();
    for (int num : array) {
      sb.append(num);
    }
    return Integer.parseInt(sb.toString());
  }
}

JavaScript

var maximumSwap = function(num) {
  let maxNum = num;
  let numArray = num.toString().split('');
  const size = numArray.length;

  for (let i = 0; i < size - 1; i++) {
    for (let j = i + 1; j < size; j++) {

      // swap
      let tmp = numArray[i];
      numArray[i] = numArray[j];
      numArray[j] = tmp;

      // 숫자를 다시 정수로 변환하여 최대값과 비교 후 갱신
      maxNum= Math.max(maxNum, parseInt(numArray.join('')))

      // 다시 원 위치
      tmp = numArray[i];
      numArray[i] = numArray[j];
      numArray[j] = tmp;

    }
  }

  return maxNum;

};