문제 설명
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 해야 합니다.
나의 풀이
이진 변환에 대한 알고리즘을 어떻게 만들까..? 고민하던 찰나에 친절하게도 Integer.toBinaryString 이라는 기능이 있어서 큰 도움이 됐다. ‘0’을 없애는 과정과 다시 없앤 문자열을 이진 변환을 하는 과정이 여러 번 반복될 것을 알았기에 재귀함수를 적용하여 풀어보기로 했다!
풀이는 비교적 간단했는데 코드는 다음과 같다.
import java.util.Arrays;
class Solution {
int cnt = 0;
int zeroCnt = 0;
public int[] solution(String s) {
int[] answer = new int[2];
recursive(s);
answer[0] = cnt;
answer[1] = zeroCnt;
return answer;
}
public void recursive(String s) {
if (s.equals("1")) {
return;
}
String tmp = Integer.toBinaryString(convert(s).length());
cnt++;
recursive(tmp);
}
public String convert(String s) {
String tmp = "";
for (String str : s.split("")) {
if (str.equals("0")) {
zeroCnt++;
continue;
}
**else {**
**tmp += str;**
}
}
return tmp;
}
}재귀 탈출 조건은 문제에서 요구하는 문자열이 ‘1’이 됐을 때로 정하였다. 그후 재귀함수 내부에서 ‘0’을 제거해줄 convert 메서드를 만들었는데, ‘0’이 아닌 ‘1’이 왔을 경우 tmp 문자열에 계속해서 담아주는 부분에서 메모리 낭비가 발생하는 뭔가 아쉬웠다.
String은Heap메모리 영역에서String Pool이라는 곳에 저장이 되는데, 이는 곧convert함수에 의해 각기 다른tmp문자열이 계속해서String Pool에 생성되고 있다는 것이다.이왕 재귀를 통해 계속해서 생성될 것이라면 동기화 환경이 아닌 단일 쓰레드 환경에서는
StringBuilder가 더 효율이 좋기 때문에 이를StringBuilder로 바꿔준다면 보다 나은 코드가 될 것이라고 생각한다!
