이진 변환 반복하기

작성일: 2024-10-14

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

문제에 대한 내용

문제 설명

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

x의 모든 0을 제거합니다.
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’이 최소 하나 이상 포함되어 있습니다.

입출력 예

s	result
“110010101001”	[3,8]
“01110”	[3,3]
“1111111”	[4,1]

입출력 예 설명

입출력 예 #1

“110010101001”이 “1”이 될 때까지 이진 변환을 가하는 과정은 다음과 같습니다.

회차	이진 변환 이전	제거할 0의 개수	0 제거 후 길이	이진 변환 결과
1	“110010101001”	6	6	“110”
2	“110”	1	2	“10”
3	“10”	1	1	“1”

3번의 이진 변환을 하는 동안 8개의 0을 제거했으므로, [3,8]을 return 해야 합니다.

입출력 예 #2

“01110”이 “1”이 될 때까지 이진 변환을 가하는 과정은 다음과 같습니다.

회차	이진 변환 이전	제거할 0의 개수	0 제거 후 길이	이진 변환 결과
1	“01110”	2	3	“11”
2	“11”	0	2	“10”
3	“10”	1	1	“1”

3번의 이진 변환을 하는 동안 3개의 0을 제거했으므로, [3,3]을 return 해야 합니다.

입출력 예 #3

“1111111”이 “1”이 될 때까지 이진 변환을 가하는 과정은 다음과 같습니다.

회차	이진 변환 이전	제거할 0의 개수	0 제거 후 길이	이진 변환 결과
1	“1111111”	0	7	“111”
2	“111”	0	3	“11”
3	“11”	0	2	“10”
4	“10”	1	1	“1”

4번의 이진 변환을 하는 동안 1개의 0을 제거했으므로, [4,1]을 return 해야 합니다.

접근 방식

먼저 주어진 문자열에서 0을 제거한다.
제거된 문자열의 길이를 이진수로 변경한다.
위의 1,2번 로직을 문자열이 1이 될 때까지 반복한다.
반복 과정에서의 반복 횟수, 0 제거 수를 배열에 담아 리턴한다.

잘못된 접근

제거된 문자열을 이진수로 변경하는 과정에서 애를 많이 먹었다..
내가 사용했던 방법은 while문을 돌면서 먼저 0을 제거하고, 제거된 문자열을 while문에 넣고 몫과 나머지를 구해서 이진수를 구현하는 방식이었다.

하지만, 어찌된 구현 과정에서 1시간이상이 소모되어서, 뭔가 쉬운 방법이 있을 것 같아서 다른 사람들의 풀이를 봤다.

잘 된 접근

간단하게 메소드 하나로 바이너리를 구현할 수 있는 것을 확인할 수 있었다.

Integer.toBinaryString(1);

Integer에서 지원하는 toBinaryString() 메소드를 사용하면 아주 쉽게 바이너리로 변경이 가능했다..

결과

소스 코드

import java.util.*;
class Solution {
    public int[] solution(String s) {
        int[] answer = new int[2];
        int cnt = 0;
        int cnt2 = 0;
        while(!s.equals("1")){
            int tmp = s.length();
            s = s.replace("0", "");
            int tmp2 = s.length();
            cnt2 += tmp - tmp2;
            s = Integer.toBinaryString(tmp2);
            cnt++;
        }
        answer[0] = cnt;
        answer[1] = cnt2;
        return answer;
    }
}

주어진 문자열을 replace 메소드를 활용해 0을 모두 제거한다.
이전 문자열의 길이와 현재 문자열의 길이를 비교해서 제거된 0의 숫자를 cnt2에 더한다.
0이 제거된 문자열의 길이로 toBinaryString() 메소드로 다시 바이너리 문자열로 변경한다.
위 1,2,3 과정을 주어진 s 문자열이 1이 될 때까지 반복한다.
이후 결과를 answer 배열에 담아 리턴한다.

결과 이미지

alt text

알게 된 점

Integer의 toBinaryString 라는 메소드를 이용하면 숫자를 바이너리 문자열로 변경이 가능하다!!