[TDD로 알고리즘 문제풀기] 이진 변환 반복하기

문제

• 이진 변환 반복하기

1. 원하는 것

• s가 "1"이 될 때까지 계속해서 s에 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 return 하도록 solution 함수

2. 아는 것

• 0과 1로 이루어진 어떤 문자열 s

• 돌려받는 배열에서 앞의 숫자는 n번 변환했는 지, 뒤는 0의 개수를 세야함

3. 조건

• s의 길이는 1 이상 150,000 이하입니다.
• s에는 '1'이 최소 하나 이상 포함되어 있습니다.

4. 계획

1. 0을 카운팅한다.

2. 0을 제거한 후, 길이를 재서 1이 아니면 이진 변환을 한다.

3. 위 과정을 반복한다. -> reduce와 재귀적 반복이 필요함.

4. 어떤 값이 변화하고 있는 지(상태 변경)

   • 1. 사라진 0의 개수
   • 2. 0이 제거된 문자열 s의 길이를 이진법으로 변환한 값(이진 변환 대상)
   • 3. 이진 변환 대상의 횟수

-> 이진 변환 대상의 횟수를 구하는 게 가장 쉬워보임.

1. 이진 변환 대상의 횟수를 구하는 함수 테스트

test('count binary state solution', () => {
  expect(solution1('1')).toEqual(0);
  expect(solution1('11')).toEqual(2);
  expect(solution1('01110')).toEqual(3);
});

그리고 함수 구현

function CountBinaryState(s) {
  let count = 0;

  while (s !== '1') {
    s = (([...s].filter((i) => i !== '0')).length).toString(2);

    count += 1;
  }

  return count; 
}

2. 사라진 0의 개수를 구하는 함수부터 간단하게 테스트

test('count disappear 0 solution', () => {
  expect(solution2('1')).toEqual(0);
  expect(solution2('11')).toEqual(1);
  expect(solution2('01110')).toEqual(3);
  expect(solution2('110010101001')).toEqual(8);
});

function CountZero(s) {
  let zeroCount = 0;

  while (s !== '1') {
    zeroCount += [...s].filter((i) => i === '0').length;

    s = (([...s].filter((i) => i !== '0')).length).toString(2);
  }
  return zeroCount;
}

그럼 이 두개를 합치면 원하는 결과가 나오게 됨. 테스트 작성

test('all solution', () => {
  expect(solution('110010101001')).toEqual([3, 8]);
  expect(solution('01110')).toEqual([3, 3]);
});

function solution(s) {
  let count = 0;
  let zeroCount = 0;

  while (s !== '1') {
    zeroCount += [...s].filter((i) => i === '0').length;

    s = (([...s].filter((i) => i !== '0')).length).toString(2);

    count += 1;
  }

  return [count, zeroCount];
}

다른 방법으로도 풀 수 있지 않을까? 재귀적으로 풀어도 될 수 있어보임. (reduce도)

function solution2(s, count = 0, zeroCount = 0) {
  if (s === '1') {
    return [count, zeroCount];
  }

  return solution2(
    (([...s].filter((i) => i !== '0')).length).toString(2),
    count + 1,
    zeroCount + [...s].filter((i) => i === '0').length,
  );
}

생각을 잘 쪼개서 나누는 게 중요하다.