99클럽 코테 스터디 33일차 TIL + 정렬(Reordered Power of 2)

오늘의 과제

리트코드 medium으로 분류된 Reordered Power of 2 입니다.

 

이번 유형도 정렬입니다.

문제

https://leetcode.com/problems/reordered-power-of-2/description/

 

 

먼저 문제 요구사항 요약입니다.

 

정수가 주어질 때 2의 거듭제곱을 만들 수 있는지 여부를 반환하면 됩니다.

 

거듭제곱 여부를 쉽게 확인하기 위해 미리 2의 30제곱까지 구해둡니다. 30제곱까지만 구하는 이유는 입력으로 최대 10의 9승(10억)까지만 주어지기 때문입니다. 또한 임의의 정렬이라고 했으나 모두 통일하여 정렬하기 위해 2의 거듭제곱을 오름차순으로 정렬하여 넣어줍니다.

List<String> powerOf2Digits = new ArrayList<>();
for (int i = 0; i < 31; i++) {  // 2^0부터 2^30까지
    powerOf2Digits.add(sortedDigits(1 << i));
}

 

그 후 입력받은 정수를 똑같이 오름차순으로 정렬한 후 기존 리스트에 넣어둔 값과 일치하는지 확인합니다.

String sortedN = sortedDigits(N);

// N의 정렬된 자릿수가 2의 거듭제곱의 정렬된 자릿수 중 하나와 일치하는지 확인
for (String powerDigits : powerOf2Digits) {
    if (sortedN.equals(powerDigits)) {  // 일치하면 true 반환
        return true;
    }
}

 

정렬을 도와주는 함수입니다.

private String sortedDigits(int num) {
    char[] digits = String.valueOf(num).toCharArray();
    Arrays.sort(digits);  // 자릿수를 오름차순으로 정렬
    return new String(digits);  // 정렬된 자릿수를 문자열로 반환
}

 

 

 

코드입니다.

class Solution {
    public boolean reorderedPowerOf2(int N) {
        // 2의 거듭제곱을 문자열로 변환한 후 각 자릿수를 정렬한 결과 리스트
        List<String> powerOf2Digits = new ArrayList<>();
        for (int i = 0; i < 31; i++) {  // 2^0 부터 2^30까지
            powerOf2Digits.add(sortedDigits(1 << i));
        }

        // 주어진 정수 N의 자릿수를 정렬한 결과
        String sortedN = sortedDigits(N);

        // N의 정렬된 자릿수가 2의 거듭제곱의 정렬된 자릿수 중 하나와 일치하는지 확인
        for (String powerDigits : powerOf2Digits) {
            if (sortedN.equals(powerDigits)) {
                return true;
            }
        }
        return false;
    }

    // 숫자의 자릿수를 정렬한 문자열을 반환하는 헬퍼 함수
    private String sortedDigits(int num) {
        char[] digits = String.valueOf(num).toCharArray();
        Arrays.sort(digits);
        return new String(digits);
    }
}

 

배운 점

이전에 시프트 연산이 나온 이후 또 나올까? 생각했는데 은근히 많이 등장하고 있습니다. 시프트 연산을 활용하지 못했다면 거듭제곱을 구하기 위해 다른 방법을 써야 했을텐데 아는만큼 조금 다양한 풀이 방법이 나오는 것 같습니다. 또 사용할 일이 나올 수 있으니 정리합니다.

 

<< 해당 비트열을 왼쪽으로 이동시키고 빈 공간은 0으로 채운다.

>> 해당 비트열을 오른쪽으로 이동시키고 빈 공간은 음수는 1, 양수는 0으로 채운다.

>>> 해당 비트열을 오른쪽으로 이동시키고 빈 공간은 0으로 채운다.

 

 

오늘의 한줄평

기록하자. 어필이 아닌 내 기억을 위해.