[프로그래머스] JavaScript Lv2 - 이진 변환 반복하기(70129)

개요

문제 이름: 이진 변환 반복하기 (70129)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/70129
플랫폼: 프로그래머스
알고리즘 분류: 일반
소요 시간: 1시간

 

문제 전문

설명

제한사항

입출력

 

 

문제 풀이

해설

이 문제는 문자열 변환과 반복 처리를 요구하는 알고리즘 문제입니다. 주어진 이진 문자열에 대해 특정 규칙에 따라 변환을 반복하고, 그 과정에서 발생하는 변화를 추적해야 합니다.

 

문제를 해결하기 위해서는 아래와 같은 접근 방식이 필요합니다.

• 문자열에서 0을 제거하는 과정
• 남은 1의 개수를 세는 과정
• 1의 개수를 다시 이진 문자열로 변환하는 과정
• 이 과정을 반복하면서 변환 횟수와 제거된 0의 개수를 추적하는 과정

 

문제에서 실질적으로 요구하는 내용은 다음과 같습니다.

• 주어진 이진 문자열 s에 대해 "1"이 될 때까지 변환을 반복합니다.
• 각 변환 단계에서 다음을 수행
  • 문자열에서 모든 0을 제거합니다.
  • 제거 후 남은 문자열의 길이를 이진수로 변환합니다.
• 최종적으로 변환 횟수와 제거된 총 0의 개수를 반환합니다.

이 문제는 문자열 처리와 반복문을 활용하여 해결할 수 있습니다. JavaScript의 문자열 메서드와 정규 표현식을 사용하면 효율적으로 구현할 수 있습니다.

 

시도

1차 시도  (성공)

function solution(s) {
    // 제거된 0의 개수를 저장하는 변수
    let zeroCount = 0;
    // 변환 횟수를 저장하는 변수
    let transformCount = 0;

    // s가 "1"이 될 때까지 반복
    while (s !== "1") {
        transformCount++; // 변환 횟수 증가

        // 0 제거 및 카운트
        const beforeLength = s.length; // 0 제거 전 길이 저장
        s = s.replace(/0/g, ""); // 모든 0을 제거
        zeroCount += beforeLength - s.length; // 제거된 0의 개수 계산

        // 현재 문자열의 길이를 2진법으로 변환
        s = s.length.toString(2);
    }

    // [변환 횟수, 제거된 0의 개수] 반환
    return [transformCount, zeroCount];
}

 

대략적으로 다음과 같다고 할 수 있습니다.

1. zeroCount와 transformCount 변수를 초기화하여 각각 제거된 0의 개수와 변환 횟수를 추적합니다.
2. while 루프를 사용하여 s가 "1"이 될 때까지 변환 과정을 반복합니다.
3. 각 반복마다의 과정
   1. transformCount를 증가시켜 변환 횟수를 기록합니다.
   2. beforeLength에 현재 문자열의 길이를 저장합니다.
   3. replace(/0/g, "")를 사용하여 모든 0을 제거합니다. 여기서 정규 표현식 /0/g는 전역(g)에서 모든 0을 찾습니다.
   4. 제거된 0의 개수를 계산하여 zeroCount에 누적합니다.
4. toString(2)를 사용하여 남은 문자열의 길이를 이진수로 변환합니다.

시간 복잡도: O(n * log n). 여기서 n은 입력 문자열의 길이. 각 반복에서 문자열의 길이가 대략 절반으로 줄어들기 때문에 로그 시간이 걸림.

공간 복잡도: O(1). 추가적인 공간을 쓰지 않음.

 

2차 시도  (성공)

function solution(s) {
    // c: 변환 횟수, z: 제거된 0의 개수를 저장하는 변수
    let [c, z] = [0, 0];

    // s가 "1"이 될 때까지 반복
    while (s !== "1") {
        // s를 0을 기준으로 분할하고, 그 길이에서 1을 빼면 제거된 0의 개수
        // 예: "101" -> ["1", "1"] (길이 2) -> 2 - 1 = 1 (0 하나 제거됨)
        z += s.split("0").length - 1;

        // 정규표현식으로 1만 남기고, 그 개수를 2진수로 변환
        // match(/1/g): 모든 1을 배열로 반환
        // length: 1의 개수 (즉, 0을 제거한 후의 길이)
        // toString(2): 그 길이를 2진수 문자열로 변환
        s = s.match(/1/g).length.toString(2);

        // 변환 횟수 증가
        c++;
    }

    // [변환 횟수, 제거된 0의 개수] 반환
    return [c, z];
}

2번째 접근 방식은 1번째 방식보다 더 간결하고 효율적입니다.

1. 배열 구조 분해를 사용하여 c(변환 횟수)와 z(제거된 0의 개수)를 초기화합니다.
2. while 루프를 사용하여 s가 "1"이 될 때까지 변환 과정을 반복합니다.
3. 각 반복마다의 과정
   1. s.split("0").length - 1을 사용하여 제거된 0의 개수를 계산합니다. 이 방법은 문자열을 0으로 나누고 결과 배열의 길이에서 1을 빼는 방식으로 0의 개수를 세는 효율적인 방법입니다.
   2. s.match(/1/g)를 사용하여 모든 1을 배열로 추출하고, 그 길이를 가져와 남은 1의 개수를 계산합니다.
   3. toString(2)를 사용하여 1의 개수를 이진수 문자열로 변환합니다.
   4. 변환 횟수 c를 증가시킵니다.
4. 루프가 종료되면 [변환 횟수, 제거된 0의 개수]를 배열로 반환합니다.

이 솔루션의 시간 복잡도도 O(n * log n)입니다. 하지만 실제 실행 시간은 첫 번째 방법보다 빠를 수 있습니다. 공간 복잡도는 O(n)입니다. split과 match 메서드가 새로운 배열을 생성하기 때문입니다.

 

시간 복잡도: O(n * log n) . 다만 실제 실행 시간은 첫 번째 방법보다 빠를 수 있음.

공간 복잡도: O(n). split과 match 메서드가 새로운 배열을 생성하기 때문.

 

사용한 메서드 설명

• split(separator): 문자열을 지정된 구분자를 기준으로 나누어 배열로 반환합니다.
• match(regexp): 문자열에서 정규 표현식과 매치되는 부분을 찾아 배열로 반환합니다.
• toString(radix): 숫자를 지정된 진법의 문자열로 변환합니다. 여기서는 2진법을 사용합니다.