이진 변환 반복하기

Posted on Edited on In , ,

문제정의

문자열 x에 대한 이진변환을 1이 될 때까지 시행한다. 이진 변환은 아래와 같이 정의한다. 1. x의 모든 0을 제거한다. 2. x의 길이를 c라 하면, x를 c를 2진법으로 표현한 문자열로 바꾼다.

시행 뒤에 시행 횟수와 제거된 0의 개수를 반환하면 된다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package level2;

public class RepeatBinary {

    //프로그래머스 문제풀이 level2 이진 변환 반복하기
    public static void main(String[] args) {
        String s = "110010101001";
        int[] answer = new int[2];
        int cnt = 0, l, zero = 0;
        while(!s.equals("1"))
        {
            cnt++;
            l = s.length();
            s = s.replace("0", "");
            zero += l - s.length();
            s = Integer.toBinaryString(s.length());
        }
        answer[0] = cnt;
        answer[1] = zero;
    }
    
}
cnt는 반복횟수이고, zero는 제거된 0의 개수이다. 문자열이 1이 될 때까지 cnt를 1씩 늘려가며 2진변환을 반복한다. 0의 개수를 세기 위해 문자열에서 0을 제거하고, 그전 문자열의 길이에서 1번과정을 거친 문자열의 길이를 제거한 값을 더한다. 그리고 2번과정을 시행한다.

시간복잡도를 정하기엔 애매한 부분이 있다. 0이 몇개나 생길지 모르기 때문에 절대적으로 얼마나 n이 커질지 단정짓기가 힘들다. 더 공부가 필요하다.

테스트