Programmers / Level 2 / 이진 변환 반복하기

[문제 설명]

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'이 최소 하나 이상 포함되어 있습니다.

[입출력 예]

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

 

---

 

 

처음 코드를 짰을 땐

우선 처음 주어진 문자열 x에서 1인 수만 list에 넣고, 0인 수가 나오는 경우엔 zeroCnt를 늘려주었다.

 

그 후, 그 수를 Integer.toString(int n, int radix)를 통해 이진변환을 해주고

또 0을 제거해주었다.

0을 제거하는 과정이 계속 반복되기 때문에 메소드를 하나 따로 생성해 사용하는 방식으로 프로그램을 작성했다.

import java.util.ArrayList;

class Solution {
    static int zeroCnt;
    static int changeCnt;
    
        static public ArrayList<Integer> solution(String s) {
        changeCnt = 1;

        ArrayList<Character> list = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '1') {
                list.add(c);
            }

            else {
                zeroCnt++;
            }
        }

        int len = list.size();
        while (true) {
            // 이진 변환
            s = Integer.toString(len, 2);
            if (s.equals("1")) {
                break;
            }
            len = removeZero(s);
        }
        ArrayList<Integer> answer = new ArrayList<>();
        answer.add(changeCnt);
        answer.add(zeroCnt);
        
        return answer;
    }

    // 0 제거하는 메소드
    private static int removeZero(String s) {
        ArrayList<Character> list = new ArrayList<>();

        changeCnt++;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '1') {
                list.add(c);
            } else {
                zeroCnt++;
            }
        }
        return list.size();
    }
}

 

---

 

문제 난이도보다 좀 복잡하게 푼 감이 없지 않아 있다고 생각해서

다른 사람들 풀이를 봤는데,

굳이 list를 따로 만들지 않고 주어진 대로 answer 배열만 이용해서 풀 수도 있었다.

 

내가 zeroCnt를 하나씩 더해줬던 것 처럼

while문을 돌면서 0이 나오면 answer[1] 값을 1씩 더해주었다.

1이 나온 경우엔 길이를 늘려서 그 값을 이진변환 한 후, s를 업데이트 해주는 방식이고

for문을 한 번 돌 때 마다 answer[0] 값을 1씩 더해줌으로써 이진 변환 횟수 또한 해결할 수 있다.

 

class Solution {
        static public int[] solution(String s) {
        int[] answer = new int[2];

        while (s.length() > 1) {
            int cnt = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '0') {
                    answer[1]++;
                } 
                else {
                    cnt++;
                }
            }

            s = Integer.toString(cnt, 2);
            answer[0]++;
        }

        return answer;
    }
}

 

훨씬 간단해진 코드이다!