[프로그래머스/Lv. 2] 이진 변환 반복하기

🔺 문제

프로그래머스

 

🔺 코드

- 틀림

import java.util.*;

class Solution {
    public int[] solution(String s) {
        
        int zeroCnt = 0;    // 제거할 0의 갯수
        int turn = 0;       // 회차
        int len = 0;        // 0 제거 후 길이
        
        // 이진 변환 반복
        int num = Integer.parseInt(s);
        for(int i = 1 ; ; i++) {
            if(Integer.bitCount(num) != s.length()) { // 0이 존재한다면
                zeroCnt += s.length() - Integer.bitCount(num);    // 제거할 0의 갯수 더하고
                s = s.replace("0", "");             // 0 제거하기
                len = s.length();                   // 0 제거 후 길이
                num = Integer.parseInt(Integer.toBinaryString(len));    // 이진 변환 결과
                turn = i;
                
                if(num == 1) {
                    break;
                }
            }
        }
        
        int[] answer = new int[2];
        answer[0] = turn;
        answer[1] = zeroCnt;
        
        return answer;
    }
}

시간 초과 에러가 떴다.

 

 

- 정답

class Solution {
    public int[] solution(String s) {
        int[] answer = new int[2];
        
        while(s.length() > 1) { 
            int cntOne = 0;     // 1 갯수 세기
            
            for(int i = 0 ; i < s.length() ; i++) {
                if(s.charAt(i) == '0') answer[1]++;
                else                   cntOne++;
            }
            
            s = Integer.toBinaryString(cntOne);
            answer[0]++;
        }
        
        return answer;
    }
}

✅ 해결 아이디어
- 반복문 범위 : s가 1이 아닐 때까지 / s의 길이가 1보다 클 때까지 반복하면 됨
- 회차 구하기 :  반복문 마지막에 answer[0]++ 해주면 쉬워짐
- 여기서 1의 개수 = 0 제거 후 길이

---

🔺 다른 풀이들

- 풀이1)

class Solution {
    public int[] solution(String s) {
        int[] answer = new int[2];
        int temp;
        
        while( !s.equals("1") ) {
            answer[1] += s.length();
            s = s.replaceAll("0", "");		// 0 제거
            temp = s.length();			// 0 제거 후 길이 = 1의 개수
            s = Integer.toBinaryString(temp);	// 십진수를 이진수로 변환

            answer[0]++;			// 회차
            answer[1] -= temp;			// 전체 - 1의 개수 = 0의 개수
        }
        
        return answer;  
    }
}

 

 

- 풀이2) 재귀함수

class Solution {
    public static int count;
    public static int zeroCount;
    
    public int[] solution(String s) {
        int[] answer = new int[2];
        count = 0;
        zeroCount = 0;
        recursive(s);
        
        answer[0] = count;
        answer[1] = zeroCount;
        return answer;
    }
    
    public static void recursive(String s){
        if(s.equals("1"))
            return;
        
        count++;
        
        StringBuilder sb = new StringBuilder();
        for(char c : s.toCharArray()){
            if(c == '0'){
                zeroCount++;
                continue;
            }
            sb.append(c);
        }
        recursive(Integer.toBinaryString(sb.length()));
    }
}

재귀함수랑 StringBuilder랑 toCharArray() 사용하심