[Leetcode]3309. Maximum Possible Number by Binary Concatenation

문제 요약

• 알고리즘 분류:  이진법, 베열 
• 난이도: Medium
• 문제내용:
  • 주어진 크기가 3인 정수 배열의 요소들을 이진수로 변환하고, 이들을 다양한 순서로 이어 붙여 만들 수 있는 숫자 중 가장 큰 값을 찾아 반환하여라
• 사이트 주소: https://leetcode.com/problems/maximum-possible-number-by-binary-concatenation/description/

문제풀이

이번 문제는 3개수를 각 이진법으로 변환하여  여러가지 순서로 이어붙인 다음  10진수로 변환 한것중 가장 큰것을 구하면 된다. 그럼 크게 2가지만 구현 하면된다.

1. 3개 숫자 2진수 변환후 이어 붙이 다음 10진수로 변환
2. 3개 숫자 순열구현

1.  3개 숫자 2진수 변환후 이어 붙이 다음 10진수로 변환

 직업 진법을 변환 할수 있지만 각 언어별로 진법 변환 시켜주는 함수들이 있다. 그 함수들을 활용 해보자.

Python

 파이썬에서는 이진수로 변환할 때 bin 함수를 사용할 수 있습니다. 하지만 bin 함수로 변환된 결과는 '0b'라는 접두사가 붙은 문자열 형태로 반환된다. 따라서 이진수 부분만 사용하려면 문자열의 두 번째 인덱스부터 가져와야 한다. 이후, int(문자열, 진법)을 사용하면 해당 문자열을 지정된 진법에서 10진수로 변환할 수 있다.

binary_string = ''.join(map(lambda x: bin(x)[2:], arr))
decimal = int(binary_string, 2)

Java

Integer.toBinaryString(정수): 2진수로 변경 해준다.

Integer.parseInt(문자열 , 진법 ): 해당 문자열을 지정된 진법에서 10진수로 변환할 수 있다.

public int binaryConcatenation(int a1, int a2, int a3){

    StringBuilder binary = new StringBuilder();
    binary.append(Integer.toBinaryString(nums[a1]));
    binary.append(Integer.toBinaryString(nums[a2]));
    binary.append(Integer.toBinaryString(nums[a3]));

    return Integer.parseInt(binary.toString(), 2);  // 이진수 문자열을 10진수로 변환하여 반환
}

2.  3개 숫자 순열 구현

 순열 구현할수 있지만 3개 숫자인데 경우의 수가 총 6가지 된다. 인덱스 0, 1, 2 기준으로 아래 6개로 표현 할수 있다.

• 0, 1, 2
• 0, 2, 1
• 1, 0, 2
• 1, 2, 0
• 2, 0, 1
• 2, 1, 0

위 두개만 구현만 하면 문제 푸는데는 어렵지 않다. 자세한것은 아래 코드에서 참고 하면된다.

Code

Python

 밑에 자바 코드처럼 각 6가지 경우의 수로 구현 할 수 있지만 파이썬에서는 순열 제공 해주는 permutations 함수가 있다.

class Solution:
    def maxGoodNumber(self, nums: List[int]) -> int:
        
        max_value = 0

        # nums 배열의 모든 순열 생성
        for arr in permutations(nums):
            # 각 순열의 숫자들을 이진수 문자열로 변환하여 연결
            binary_string = ''.join(map(lambda x: bin(x)[2:], arr))
            # 이진수 문자열을 10진수로 변환하여 최댓값 갱신
            max_value = max(max_value, int(binary_string, 2))

        return max_value

Java

class Solution {

   int[] nums;
    public int maxGoodNumber(int[] nums) {

        this.nums = nums;

        // 0, 1, 2의 모든 순열에 대해 binaryConcatenation 값을 계산하고, 최댓값을 구함
        int maxValue = binaryConcatenation(0, 1, 2);
        maxValue = Math.max(maxValue, binaryConcatenation(0, 1, 2));
        maxValue = Math.max(maxValue, binaryConcatenation(0, 2, 1));
        maxValue = Math.max(maxValue, binaryConcatenation(1, 0, 2));
        maxValue = Math.max(maxValue, binaryConcatenation(1, 2, 0));
        maxValue = Math.max(maxValue, binaryConcatenation(2, 0, 1));
        maxValue = Math.max(maxValue, binaryConcatenation(2, 1, 0));

        return maxValue;
    }

    // 세 숫자의 인덱스를 받아 바이너리 문자열로 연결한 후 10진수 값으로 변환하는 메서드
    public int binaryConcatenation(int a1, int a2, int a3){

        StringBuilder binary = new StringBuilder();
        binary.append(Integer.toBinaryString(nums[a1]));
        binary.append(Integer.toBinaryString(nums[a2]));
        binary.append(Integer.toBinaryString(nums[a3]));

        return Integer.parseInt(binary.toString(), 2);  // 이진수 문자열을 10진수로 변환하여 반환
    }
}