[프로그래머스] L2 이진 변환 반복하기

문제

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

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

예를 들어, x = "0111010"이라면, x에 이진 변환을 가하면 x = "0111010" -> "1111" -> "100" 이 됩니다.

0과 1로 이루어진 문자열 s가 매개변수로 주어집니다. s가 1이 될 때까지 계속해서 s에 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 150,000 이하입니다.
• s에는 '1'이 최소 하나 이상 포함되어 있습니다.

풀이

사실 처음 문제를 풀 때 문제를 대충 읽어서 정확히 이해가 되지 않았었습니다. 예시를 들어 다시 내용을 설명해보겠습니다.

1. x = "0111010"
2. 0을 제거합니다 = "1111"
3. "1111"의 길이 = 4 (1이 4개)
4. 4를 이진수로 표현하면 = "100"

이 과정을 결과가 1이 될 때까지 반복하면됩니다. 이 때 반복한 횟수와 제거된 0의 전체 갯수를 구하는 문제입니다.

방식1

문제를 보면 아시겠지만 0을 제거한 String을 굳이 만들어낼 필요는 없습니다. 현재 string에서 0의 수를 파악한 후 현재 길이에서 0의 수를 뺀 값을 다시 binary string으로 만드는 작업을 반복하면 풀 수 있을 것으로 생각됩니다. 이와 같은 방법으로 풀면 아래와 같습니다.

private int countingZero(String number) {
    int zero = 0;

    for (char c : number.toCharArray()) {
        if (c == '0') zero++;
    }

    return zero;
}

public int[] solution(String s) {
    int[] answer = new int[2];
    int zero;
    String number = s;

    while(number.length() != 1) {
        zero = countingZero(number);
        ++answer[0];
        answer[1] += zero;
        number = Integer.toBinaryString(number.length() - zero);
    }

    return answer;
}

 

방식2

위와 같은 방법으로 풀어보니 굳이 int를 binary string으로 변환해야 하는가? 비트 연산으로도 풀 수 있겠다는 생각이 들었습니다. 그렇다면 사실 string으로 변환 작업이 필요가 없기 때문입니다. 하지만 이렇게 할 경우 문제가 1가지 있습니다. 첫 인풋 string에서 0으로 시작하는 input이 들어온다는 것입니다. 길이를 binary로 변경할 경우 1앞에 0이 오는 경우는 없습니다. 하지만 첫 인풋에서 string이기 때문에 "000010" 과 같이 0이 앞에 올 수 있는 문제가 있기 떄문에 첫 번째 처리는 방식 1과 같이 진행해야 할 것으로 보여졌습니다. 이와 같은 방식을 풀면 아래와 같습니다.

private int countingZero(String number) {
    int zero = 0;

    for (char c : number.toCharArray()) {
        if (c == '0') zero++;
    }

    return zero;
}

public int[] solution(String s) {
    int[] answer = new int[2];
    int temp;
    int one;

    temp = countingZero(s);
    ++answer[0];
    answer[1] += temp;
    int input = s.length() - temp;

    while(input != 1) {
        temp = input;
        one = 0;
        ++answer[0];
        while(temp > 0) {
            if ((temp & 1) == 1) {
                ++one;
            } else {
                ++answer[1];
            }
            temp >>= 1;
        }
        input = one;
    }

    return answer;
}

 

결과

방식1

방식2

정수를 바이너리 스트링으로 변경하는 과정이 빠져서 훨씬 빠를거라고 생각했었는데 결과는 큰차이가 없는 것으로 보여지네요