작성일 : 2024.12.03

이진 변환 반복하기

문제 설명

이진수 문자열에 대해 다음과 같은 이진 변환을 반복적으로 수행합니다:

1. 모든 0을 제거
2. 남은 문자열의 길이를 2진수로 변환

이진 변환을 "1"이 될 때까지 반복하면서 다음을 계산합니다:

• 변환 횟수
• 제거된 0의 총 개수

예시

"0111010" -> "1111" (0 제거) -> "100" (길이 4의 이진수)

제한 조건

1. 입력 문자열 s
   • 길이: 1 ≤ length ≤ 150,000
   • 최소 하나의 '1' 포함
   • 0과 1로만 구성

해결 코드

function solution(s) {
  var answer = [];

  var removeZeroCount = 0; // 제거된 0의 개수
  var removeZeroTime = 0; // 변환 횟수

  while (s.length > 1) {
    var result = [];
    // 0 제거 과정
    for (var i = 0; i < s.length; i++) {
      if (s[i] == "1") {
        result.push(s[i]);
      } else {
        removeZeroCount++;
      }
    }
    removeZeroTime++;
    // 길이를 2진수로 변환
    s = result.length.toString(2);
  }

  answer = [removeZeroTime, removeZeroCount];
  return answer;
}

알고리즘 설명

1. 초기화

var removeZeroCount = 0; // 제거된 0의 총 개수
var removeZeroTime = 0; // 이진 변환 횟수

2. 변환 과정

while (s.length > 1) {
  // 1. 0 제거
  for (var i = 0; i < s.length; i++) {
    if (s[i] == "1") {
      result.push(s[i]);
    } else {
      removeZeroCount++;
    }
  }

  // 2. 변환 횟수 증가
  removeZeroTime++;

  // 3. 길이를 2진수로 변환
  s = result.length.toString(2);
}

주요 메서드 설명

1. toString(2)

// 숫자를 2진수 문자열로 변환
number.toString(2)

예시:
4.toString(2)     // "100"
10.toString(2)    // "1010"

2. 배열 메서드

result.push(s[i]); // 1을 배열에 추가
result.length; // 배열의 길이 (1의 개수)

구현 포인트

1. 0 제거 과정

   • 문자열을 순회하며 1만 보존
   • 제거된 0의 개수 카운트

2. 이진 변환

   • 남은 1의 개수(길이)를 2진수로 변환
   • toString(2) 메서드 활용

3. 종료 조건

   • 문자열이 "1"이 될 때까지 반복

시간 복잡도

• O(n * k): n은 초기 문자열 길이, k는 변환 횟수

공간 복잡도

• O(n): 임시 배열 사용

입출력 예시

입력: "110010101001";
출력: [3, 8];
// 변환 과정:
// "110010101001" -> "111111" -> "110" -> "11" -> "10" -> "1"
// 변환 횟수: 3
// 제거된 0의 개수: 8