99클럽 코테 스터디 33일차 TIL Reordered Power of 2

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

 

 

 

set

powerOf2

거듭제곱

비트쉬프트연산자

 

 

 

1. 문제 및 접근

 

 

 

 

869. Reordered Power of 2

 

 

 

integer 타입의 숫자가 하나 주어지면 String으로 생각해서

단어들을 재배열 하는데 ex) 12 = '1' '2' 12, 21이 2의 거듭제곱인지 판별해서 반환

10^9까지 들어옴 10억

기본적으로 312이 주어지면 ? 123, 132, 213, 231, 312, 321 다봐야한다

그러면 들어오는 숫자는 10억이지만 숫자는 10개 0이 먼저할 수 없는 위치에 따라

987,654,321이라면 9! = 최대 362,880개를 하나씩 다 2의 거듭제곱이 맞는 지 확인

 

2의 거듭제곱 테이블을 하나 만들고 거기서 찾자

2^30승이 10억쯤 되니 int형 최대치인 31승까지만 그냥 담자

 

먼저 들어온 숫자를 String으로 바꾸고, 순열을 재귀로 만들기

 

 

Constraints:

• 1 <= n <= 10^9 

 

 

 

 

 

2.  풀이

private static String now;
private static HashSet<String> set;

public static void main(String[] args) {
    int n = 10;


    reorderedPowerof2 main = new reorderedPowerof2();
    System.out.println(main.reorderedPowerOf2(n));
}

public boolean reorderedPowerOf2(int n) {


    set = new HashSet<>();
    now = String.valueOf(n);



    dfs("", new boolean[now.length()]);

    int[] powerOf2 = new int[31];
    int now = 2;
    powerOf2[0] = 1;
    powerOf2[1] = 2;


    for (int i = 2; i < 31; i++) {

        now = now * 2;

        powerOf2[i] = now;


        }



    for (String s : set) {

        if (s.charAt(0) != '0') {

        int check = Integer.valueOf(s);

        for (int i : powerOf2) {

            if (check == i) {

                return true;
            }}

        }

    }

    return false;

}

private void dfs(String s, boolean[] isVisited) {

    int length = now.length();

    if (s.length() == length) {

        set.add(s);

        return;

    }

    for (int i = 0; i < length; i++) { // 3번씩 계속 반복

        if (!isVisited[i]) {

            isVisited[i] = true;
            dfs(s + now.charAt(i), isVisited);
            isVisited[i] = false;
        }
    }
}

 

 

 

 

 

 

 

 

2-1. DFS(호출)

 

 

 

ex) n = 312

 

 

 

 

static set에 담아 중복을 없애줄 생각을 하였다. (상관 없을 거 같긴 하다)

static now는 현재 들어온 int형 숫자를 String 타입으로 바꿔서 저장

 

 

들어온 n를 따로 떼어주어 순열로 만들어야한다.

 

 

dfs에 빈 문자열과 지금 쓰는 수를 확인하기 위해 boolean 배열을 현재 "312"의 길이만큼 만들어서 넘김

 

 

 

312가 들어온다면 ?

 

 

"312", "321", "213", "231", "123", "132"

 

 

6개의 경우가 2의 거듭제곱인지 확인해야 하니까

 

 

 

먼저 312를 dfs로 6개의 String들을 만들어주자 !

 

 

 

 

 

 

 

2-2.  dfs(기저조건)

 

 

 

now = "312"

 

재귀를 돌면서 만들어진 s의 길이와 now의 길이가 같아진다면 set에 추가해주고 호출한 곳으로 return;

 

 

 

 

 

 

 

2-3. DFS 동작

 

 

 

 

3번씩 반복하며 계속 만들어질껀데,

 

현재 isVisited 배열은 False로 초기화된 상태다.

 

 

현재 수가 방문한 적이 없다면 (![isVisited[i])

 

 

방문 표시 이후 dfs에는 s와 현재 수를 추가하고, 방문 여부의 배열을 그대로 넘겨준다.

 

 

 

 

기저조건에서 return이 된다면 ?

 

 

하나의 수가 만들어졌단 뜻이라 다음 수를 만들어야 하기에 배열을 다시 false로 바꿔줌 ( 또 써야 하니까!)

우리는 다시 새로운 배열을 가지고, 수 조합을 또 할꺼니까~

 

 

 

 

DFS의 예시를 몇개만 보자 이해가 안되면 하나씩 따라 그려 보는 게 최고다!

 

 

now ="312"

isVisited = [false, false, false]

s = ""

 

 

 

1) DFS("", 0) 호출

• 호출 시 상태  s = "", s.length = 1 ,  isVisited = [false, false, false]
•  i=0 :
  • isVisited[0] = false이므로 가능, true로 변환
  • s = "3" 
  • isVisited = [true, false, false]
  • DFS("3", 1) 호출

 

 

 

 

2) DFS("3", 1) 호출:

 

• 호출 시 상태  s  = "3", s.lenght = 1, isVisited = [true, false, false]
•  i=0 :
  • isVisited[0] = true이므로 pass
• i=1 :
  • isVisited[1] = false이므로 가능, true로 변환
  • s = "31"
  • isVisited = [true, true, false]
  • DFS("31", 2) 호출

 

 

 

 

3) DFS("31", 2) 호출:

• 호출 시 상태  s = "31",  s.lenght = 2,  isVisited = [true, true, false]
•  
• i=0:
  • isVisited[0] = true이므로 pass
• i=1:
  • isVisited[1] = true이므로 pass
• i=2:
  • isVisited[2] = false이므로 사용
  • s = "312"
  • isVisited = [true, true, true]
  • DFS("312", 3) 호출

• DFS("312", 3) 호출:
  • 호출 시 상태 s = "312", s.lenght = 3
  • s.length() == now.length()이므로 순열 완성
  • 순열 "312"를 집합에 추가
  • 리턴하여 이전 상태로 돌아감

 

 

3-1)  DFS("31", 2)로 돌아옴

• 호출 시 상태 s = "31",  s.lenght = 2,  isVisited = [true, true, false]
•  isVisited[2]를 false로 변경
• For문 끝
• 리턴하여 이전 상태로 돌아감

 

 

중요한 점은 3)을 다 수행해서 312가 만들어졌고, 다른 값들은 다시 3)을 만들 시점과 같아진다.

 

 

만들어진 것들을 set에 저장!

 

 

 

 

 

 

 

 

 

3. 거듭제곱 테이블

 

 

 

2의 0승은 1

2의 1승은 2

 

2^30까지 만들 거라

 

현재 now =2 부터, 거듭제곱해서 배열에 저장

 

 

 

 

 

 

 

 

4. 거듭제곱 판별

 

 

 

set에 저장된  "312", "321", "213", "231", "123", "132"을 돌면서

 

 

놓칠만한 점은 0으로 시작할 순 없다는 조건이 있다.

 

현재 set에 저장된 String형태의 "312"를 int형 배열의 요소와 비교하기 위해 형 변환

 

 

현재 요소가 거듭제곱 테이블에 있다면 ?

 

retrun true;

 

다 돌고도 없다면 false 반환 !

 

 

 

 

 

 

 

4-1. 내 실수

 

 

 

s를 int형태로 변환하는 과정에서

 

주어진 n이 10이라면, 

 

"10", "01"이 set에 담길 것이다.

 

s= "01"의 예시라면,  int형으로 변환 시 

 

check = 1이 되어버려서 true를 반환한다.

 

0의 예시를 놓쳤고, 그래서 다시 짠 코드에선

 

 

s의  0 번째 index가 0이 아닐 때만 동작하게 추가해줌

 

if(s.charAt(0) != '0')

 

 

 

 

 

 

 

성공은 했는데..

말도 안되게 느리다..

DFS가 엄청 느린 것 같은데.. 거듭제곱은 얼마 안걸려서 dp해도 크게 차이나지 않을 것 같은데..

 

 

 

 

 

 

 

5.  GPT선배님의 도움

 

 

 

public boolean reorderedPowerOf2(int n) {
        String sortedInput = sortString(String.valueOf(n));

// 2의 거듭제곱 테이블 생성
        Set<String> powerOf2s = new HashSet<>();
        for (int i = 0; i < 31; i++) {
            powerOf2s.add(sortString(Integer.toString(1 << i)));
        }

// 주어진 숫자의 정렬된 형태가 2의 거듭제곱 중 하나인지 확인
        return powerOf2s.contains(sortedInput);
    }

    private String sortString(String s) {
        char[] chars = s.toCharArray();
        java.util.Arrays.sort(chars);
        return new String(chars);
    }

 

 

 

 

 

5-1. 정렬된 숫자 사용하기

 

 

 

 

 

1. 동일한 숫자 조합

숫자를 재배열하여 2의 거듭제곱이 되는지를 확인하려면, 그 숫자의 각 자리 수가 동일한지를 확인해야 합니다. 예를 들어, 숫자 312를 재배열하면 123, 132, 213, 231, 312, 321 등의 조합이 가능합니다. 이 모든 조합은 본질적으로 같은 숫자 조합을 나타냅니다.

 

 

2. 2의 거듭제곱도 같은 방법으로 확인 가능

 

2의 거듭제곱도 동일한 자리 수의 조합으로 표현될 수 있습니다. 예를 들어, 2^3 = 8은 단순히 "8"로 표현되고, 2^4 = 16은 "16"로 표현됩니다. 각 거듭제곱의 자리 수를 정렬하면 해당 거듭제곱을 구성하는 자리 수의 조합이 나타납니다.

 

 

 

 

 

 

 

 

 

5-2. 동작

 

 

 

핵심은 정렬이다.

 

정렬을 하게 된다면 어떤 순서로 배열해도 동일한 정렬된 문자열(자리수가 같다면)을 얻게되고, 2의 거듭제곱 테이블도 정렬해서 비교

 

 

 

 

ex) "312"

 

 

 

 

현재 받은 n인 "312"를 "123"으로 정렬

 

 

 

 

 

 

2의 거듭제곱 테이블을 생성하는데,

 

 

 

 

번외.  << 가 뭘까 ?

 

비트 쉬프트 연산자로,

 

<< : 피연산자의 비트열을 왼쪽으로 이동시키며 이동에 따른 빈공간은 0으로 채움.

>> : 피연산자의 비트열을 오른쪽으로 이동시키며, 이동에 따른 빈공간은 음수의경우엔 1, 양수의 경우엔 0으로 채움.

>>> : 피연산자의 비트열을 오른쪽으로 이동시키며, 이동에 따른 빈공간은 0으로 채움.

 

 

 

ex)  1 << i

 

 

i = 1,  이진수로 0001 → 0010  = 2

i = 2, 이진수로 0001 → 0100  = 4

 

2^i과 같은 연산이다.

 

 

2진수 정수의 특성상 왼쪽으로 한칸씩 비트열을 움직이면 2의 배수곱으로,

오른쪽으로 한칸씩 이동시키면 2의 배수 나눗샘이 되게 된다.

 

 

 

장점으로는 cpu 부담을 줄일 수 있다. * , / 연산자 보다 비트만 이동시키는 게 훨씬 부하가 덜 걸린다.

 

 

 

 

 

 

 

만들어진 숫자들을 정렬

 

 

• 2^0 = 1 -> "1"
• 2^1 = 2 -> "2"
• 2^2 = 4 -> "4"
• 2^3 = 8 -> "8"
• 2^4 = 16 -> "16" -> "16"
• 2^5 = 32 -> "32" -> "23"
• 2^10 = 1024 -> "1024" -> "0124"

 

 

 

 

정렬된 n ="123" 이 정렬된 거듭제곱 테이블에 있는지 여부를 확인

 

 

 

결과적으로 모든 순열을 만들지 않고, 순열을 특성을 이용해서 정렬시킨 후 비교한다면 획기적인 시간 단축이 가능하다!

 

 

 

 

 

 

 

이해가 어렵다면 쉽게 생각해보라 !

 

312는 123, 213, 132, 231, 312, 321 6개를 만들 수 있고,

 

이 6개의 수들은 정렬하면 모두 다 "123"이 된다.

 

마찬가지로 2^10 = 1024의 경우, 정렬하면 "0124"가 된다.

 

이 두 수를 비교해서 없다면, 어떤 재조합의 경우도 2의 거듭제곱 테이블에 없다는 뜻

 

(직관적이지 않아 어렵다)

 

위 GPT vs 아래 주판급

 

처참하게 졌다..

가서 서버 전원 내리고 올까?

 

 

무자비한 자식 

 

 

 

 

 

 

 

 

 

6.  마무리

 

 

역시 내가 생각하는 것과 gpt형님의 생각은 다른가보다.. 아직 개발자가 되지도 못했는데 벌써부터 벽을 느껴져서

 

gpt를 키자마자 끄고, 묻자마자 stop하고 내가 이길 수 있는 방법은 다 써서 이겨 버렸다..

(근데 이제 이런 말도 위험하다고 하는데,, 사랑해요 컴퓨타)

 

사실 어느정도 도움 받는 것은 중요한 것 같고 형님의 장점만 쏙쏙 빼먹어서 성장 해야할 것 같네

 

이길 수 없다면 부셔.. 가 아니라 올라타서 배우고 열심히 따라가자

 

잘 활용할 수 있다면 진짜 큰 도움이 되니까 어차피 우린 컴퓨터가 나온 시점부터 졌잖아 ?

 

 

 

순열의 특성에 대해 완벽하게 이해하지 못해 정렬하면 (자리수가 같다면) 거듭제곱도 정렬 시 정렬된 수로만 판별 가능하다는 것이

직관적이지 않고 이해가 힘들어서 내가 떠올리진 못할 것 같다..

 

새로운 방식으로 접근할 수 있다는 것과 재귀는 항상 어려운데 차근차근 잘 짚고 넘어가자ㅠㅠ