[PCCP] Lv2: 이진 변환 반복하기(70129) 해설

문제

- 문제 링크: 이진 변환 반복하기

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: 주어진 수

- while문에서 N이 1이 될 때까지 2로 나누므로 O(logN)

- s.replace(): O(N)

- 최종 시간 복잡도: O(NlogN)

class Solution {
    public int[] solution(String s) {
        // 이진 변환 횟수를 저장하는 변수
        int countTransform = 0;
        // 제거된 모든 0의 개수를 저장하는 변수
        int countZero = 0;
        
        // s가 '1'이 아닌 동안 계속 반복
        while (!s.equals("1")) {
            // 이진 변환 횟수를 1 증가
            countTransform++;
            // s에서 '0'의 개수를 세어 countZero에 누적
            int zero = s.replace("1", "").length();
            countZero += zero;
            // s에서 '1'의 개수를 세고, 이를 이진수로 반환. Integer.toBinaryString() 활용
            s = Integer.toBinaryString(s.length() - zero);
        }
        // 이진 변환 횟수와 제거된 모든 '0'의 개수를 배열에 담아 반환
        return new int[]{countTransform, countZero};
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: 주어진 수

- while문에서 N이 1이 될 때까지 2로 나눔: O(logN)

- s.count(): O(N)

- 최종 시간 복잡도: O(NlogN)

def solution(s):
    # 이진 변환 횟수를 저장하는 변수
    count_transform = 0
    # 제거된 모든 0의 개수를 저장하는 변수
    count_zero = 0
    
    # s가 '1'이 아닌 동안 계속 반복
    while s != "1":
        # 이진 변환 횟수를 1 증가
        count_transform += 1
        # s에서 '0'의 개수를 세어 count_zero에 누적
        count_zero += s.count("0")
        # s에서 '1'의 개수를 세고, 이를 이진수로 변환
        # bin() 함수를 사용하기 위해 0b 뒤의 문자열 활용
        s = bin(s.count("1"))[2:]
        
    # 이진 변환 횟수와 제거된 모든 '0'의 개수를 리스트에 담아 변환
    return [count_transform, count_zero]

solution 2)

def solution(s):
    answer = []
    cnt, z_cnt = 0, 0
    while True:
        cnt += 1
        z_cnt += s.count('0')
        s = s.replace('0','')
        s = str(bin(len(s)))[2:]
        if s == '1':
            return [cnt, z_cnt]

solution 3)

import

 

(JavaScript)

solution 1)

- N: 주어진 수

- while문에서 N이 1이 될 때까지 2로 나누므로 O(logN)

- s에서 '0' 혹은 '1'의 개수를 구할 때 필요한 시간 복잡도: O(N)

- 최종 시간 복잡도: O(NlogN)

function solution(s) {
    // 이진 변환 횟수를 저장하는 변수
    let countTransform = 0;
    
    // 제거된 모든 0의 개수를 저장하는 변수
    let countZero = 0;
    
    // s가 '1'이 아닌 동안 계속 반복
    while (s !== '1') {
        s = s.split(''); // 문자열을 배열로 변환
        // 이진 변환 횟수를 1 증가
        countTransform += 1;
        // s에서 '0'의 개수를 세어 countZero에 누적
        countZero += s.filter((c) => c === '0').length;
        // s에서 '1'의 개수를 세고, 이를 이진수로 변환
        s = s.filter((char) => char === '1').length.toString(2);
    }
    
    // 이진 변환 횟수와 제거된 모든 '0'의 개수를 배열에 담아 반환
    return [countTransform, countZero];
}

solution 2)

import

solution 3)

import