[프로그래머스/LV2] 이진 변환 반복하기 - 비트 구현 (Java)

[programmers-lv2] 이진 변환 반복하기

🙋‍♂️ 들어가며

말 그대로 이진 변환이라 비트관련 문제이다.

주석을 잘 읽어보면 문제 설명의 흐름이 그대로 나타나있을 것이다.

문제를 읽고 그대로 반영하였기 때문이다.

---

풀고나서 다른 답을 찾아보며 느낀건데

나의 경우 해당문제에서 이진변환을 직접 구현했으나, 성능은 내장함수가 훨씬 더 좋다고 한다.

다만 Java 비트 내장함수를 몰라서 쓰지는 못하였다. 노력을 더 해야만한다 반성하자

✅ 정답 코드 O(N^2)

class Solution {
    public int[] solution(String s) {
        int[] answer = new int[2];

        // 0. 0을 제거한 총갯수, 이진변환 총횟수
        int total_cnt_zero = 0;
        int total_round = 0;
        
        // 1. 검사 
        while (true) {
            // 1-1. s의 길이가 1이면 종료
            if (s.length() == 1) break;
            
            // 1-2. 제거할 0의 갯수 세기
            int temp_cnt_zero = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '0') temp_cnt_zero++;
            }
            total_cnt_zero += temp_cnt_zero;
            
            // 1-3. 0 제거후 길이
            int cur_leng = s.length() - temp_cnt_zero;
            
            // 1-4. 이진변환
            int power = 1;
            while (true) {
                // 1-5. 만약 2^{power-1} 까지가 cur_leng보다 작다면 정지
                if (power * 2 > cur_leng) break;
                
                // 1-6. 그렇지 않다면
                power *= 2;
            }
            
            // 1-7. cur_leng을 이진변환
            String new_s = "";
            while (true) {
                // 1-8. power == 0 이면 종료
                if (power == 0) break;
                
                // 1-9. cur_leng이 power보다 크면
                if (cur_leng >= power) {
                    cur_leng -= power;
                    new_s += 1;
                    power /= 2;
                    continue;
                }
                // 1-10. 그렇지않으면 
                new_s += 0;
                power /= 2;
                
            }
            // 1-11. new_s 갱신
            s = new_s;
            
            // 1-12. total_round 갱신
            total_round++;   
        }
        
        // 2. 답 추가
        answer[0] = total_round;
        answer[1] = total_cnt_zero;
        return answer;
    }
}