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

1. 문제

---

프로그래머스

2. 풀이 과정

---

문제에서 정의한 이진 변환을 1이 될 때까지 반복할 때, 이진변환의 횟수, 제거된 0의 갯수를 세는 문제이다.

 

문제에서 정의한 이진 변환은 다음과 같다.

1. 문자열에서 0을 제거한다.

2. 문자열을 0이 제거된 문자열의 길이를 이진법으로 표현한 문자열로 변환한다.

 

 

크게 생각할 것 없이 문제 그대로 구현하면 되는 문제이다.

바로 코드를 보자.

 

3. 내 코드

---

import java.util.*;
class Solution {
    public int[] solution(String s) {
        int zero_cnt = 0;
        int cvt_cnt = 0;
        while(!s.equals("1")) {
            // 1. 0 제거
            int temp = s.length();
            s = s.replace("0", "");
            zero_cnt += temp - s.length();
            
            // 2. s의 길이를 2진법으로 변환 
            int s_len = s.length();
            s = Integer.toString(s_len, 2);
            
            cvt_cnt++;
        }
    
        return new int[]{cvt_cnt, zero_cnt};
    }
}

시간 복잡도

• O(NlogN)

replace()을 통해 0을 제거하는 과정: O(N)

s를 "1"로 만드는 과정: (s가 1이 될때까지 2로 나누기 때문에) O(logN)

따라서 총 시간복잡도는 O(NlogN)이 된다.

 

10진수를 2진수로 변환하는 방법

1. Integer.toBinaryString()

int decimal = 25; // 변환하고자 하는 십진수
String binaryString = Integer.toBinaryString(decimal); // 2진수 문자열로 변환

 

2. Integer.toString()

int decimal = 25; // 변환하고자 하는 십진수
String binaryString = Integer.toString(decimal, 2); // 2진수 문자열로 변환