이진 변환 반복하기

문제

0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다.

1. x의 모든 0을 제거합니다.
2. x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꿉니다.

예를 들어, x = "0111010"이라면, x에 이진 변환을 가하면 x = "0111010" -> "1111" -> "100" 이 됩니다. 문자열 s가 "1"이 될 때까지 계속해서 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 반환하는 프로그램을 작성하는 문제입니다.

• 입력: 0과 1로 이루어진 문자열 s (길이 1 이상 150,000 이하)
• 출력: [이진 변환의 횟수, 제거된 모든 0의 개수] 형태의 정수 배열

링크: https://school.programmers.co.kr/learn/courses/30/lessons/70129

풀이 1: 내장 함수(replaceAll)를 활용한 시뮬레이션

자바의 replaceAll과 Integer.toBinaryString 메서드를 활용하여 문제에서 제시한 과정을 가장 짧고 직관적으로 모사하는 방법입니다.

• 0 제거 및 개수 누적: s.replaceAll("0", "")을 호출하여 0을 지운 뒤, (변환 전 길이) - (변환 후 길이)를 통해 지워진 0의 개수를 구합니다.
• 이진수 변환: Integer.toBinaryString(길이)를 사용하여 0이 제거된 길이를 다시 2진수 문자열로 바꿉니다.

코드 1

class Solution {
    public int[] solution(String s) {
        int turn = 0; 
        int cnt0 = 0; 
        
        while (!s.equals("1")) {
            int tmp = s.length(); 
            
            s = s.replaceAll("0", "");
            cnt0 += tmp - s.length();
            s = Integer.toBinaryString(s.length());
            turn++;
        }
        
        return new int[]{turn, cnt0};
    }
}

풀이 2: charAt을 활용한 카운팅

replaceAll은 정규식 검사와 새로운 String 객체 생성을 동반하므로 다소 무겁습니다. 어차피 "0은 모두 제거되고 1만 남는다"는 사실을 이용하면, 문자열을 만들지 않고 단순히 숫자만 세는 것으로 완벽하게 대체할 수 있습니다.

• 순회 및 카운팅: 문자열을 순회하며 문자가 '1'이면 ones를 증가시키고, '0'이면 제거될 운명이므로 cnt0을 증가시킵니다.
• 이진수 변환: 순회가 끝나면 남은 '1'의 개수(ones)가 곧 새로운 문자열의 길이가 됩니다. 이를 바로 이진수 문자열로 변환합니다.
• 효율성: 불필요한 문자열 객체 생성을 막고 반복문 한 번으로 0의 개수와 남은 길이를 모두 구하므로 속도와 메모리 면에서 훨씬 우수합니다.

코드 2

class Solution {
    public int[] solution(String s) {
        int turn = 0;
        int cnt0 = 0;
        
        while (!s.equals("1")) {
            int ones = 0; // 1의 개수 (곧 남은 문자열의 길이)
            
            // 문자열을 직접 순회하며 0과 1의 개수를 카운팅
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '1') {
                    ones++;
                } else {
                    cnt0++; // 0인 경우 바로 제거된 개수에 누적
                }
            }
            
            // 남은 1의 개수를 2진수 문자열로 변환
            s = Integer.toBinaryString(ones);
            turn++;
        }
        
        return new int[]{turn, cnt0};
    }
}

알고리즘 분류

문자열 (String), 구현 (Implementation), 수학 (Mathematics)