프로그래머스 - 이진 변환 반복하기

평범한 level 2문제

replaceAll이 생각보다 빠르지 않단 것을 알았다.

 

풀이 순서는 다음과 같다.

1. 문자열 s에서 0의 개수를 센다.

2. 문자열 s의 길이 - 0의 개수를 이진변환 한다.

3. 1이 되면 1,2번을 반복한 횟수와 그 떄 까지 센 0의 개수를 반환

 

내 풀이와 결과

 

class Solution {
    public int[] solution(String s) {
        // 이진 변환 횟수, 제거된 모든 0
        int[] answer = new int[2];
        int zeroCount = 0;
        int round = 0;
        
        while(true) {
            answer[0]++;
            zeroCount = 0;
            for(int i = 0; i < s.length(); i++) {
                if(s.charAt(i) == '0')
                    zeroCount++;
            }
            s = convertBinary(s.length() - zeroCount);
            answer[1] += zeroCount;
            
            if(s.compareTo("1") == 0)
                break;
        }
        return answer;
    }
    
    public String convertBinary(int len) {
        StringBuilder sb = new StringBuilder();
        while(len != 0) {
            sb.append(String.valueOf(len % 2));
            len /= 2;
        }
        return sb.reverse().toString();
    }
}

 

결과

 

다른 사람 풀이를 보는데

String class에서 제공하는 replaceAll 메소드와

Integer class에서 제공하는 toBinaryString 메소드를 쓴 짧은 코드를 봤지만

생각보다 원시적인 내 코드보다 많이 느려서 분석을 해봤다.

 

toBinaryString 만 사용한 코드와 그 결과 (내 풀이보다 조금 빠르다)

class Solution {
    public int[] solution(String s) {
        // 이진 변환 횟수, 제거된 모든 0
        int[] answer = new int[2];
        int zeroCount = 0;
        int round = 0;
        
        while(true) {
            answer[0]++;
            zeroCount = 0;
            for(int i = 0; i < s.length(); i++) {
                if(s.charAt(i) == '0')
                    zeroCount++;
            }
            s = Integer.toBinaryString(s.length() - zeroCount);
            answer[1] += zeroCount;
            
            if(s.compareTo("1") == 0)
                break;
        }
        return answer;
    }
}

 

 

replaceAll 만 사용한 코드와 그 결과 (많이 느리다.)

class Solution {
    public int[] solution(String s) {
        // 이진 변환 횟수, 제거된 모든 0
        int[] answer = new int[2];
        int zeroCount = 0;
        int round = 0;
        
        while(true) {
            answer[0]++;
            answer[1] += s.length();
            s = s.replaceAll("0", "");
            answer[1] -= s.length();
            s = convertBinary(s.length());
            if(s.compareTo("1") == 0)
                break;
        }
        return answer;
    }
    
    public String convertBinary(int len) {
        StringBuilder sb = new StringBuilder();
        while(len != 0) {
            sb.append(String.valueOf(len % 2));
            len /= 2;
        }
        return sb.reverse().toString();
    }
}

 

 

0을 세는 과정에서 내 코드는 O(N)만큼에 끝나지만

replaceAll은 O(N^2)정도의 시간이 소모되는 것 같다.

 

그래도 tle가 안 나는 선에서는 replaceAll이 훨씬 시간 소모가 적기 때문에

시간 복잡도가 충분하면 repplaceAll로 코드 짜는 시간을 절약하자.