비밀지도, 이진변환 반복하기

김민준·2023년 11월 28일

알고리즘 코딩테스트 프로그래머스

코드테스트

목록 보기

9/37

비밀지도
이진변환 반복하기

공부하며 느낀 점
참조한페이지

[1차] 비밀지도

그냥 5자리 수 2진수 5개를 2세트 줄테니 0만 있는건 공백 아닌건 #으로 표시해서 내달라는 것이다.

나의 풀이

10진법으로 준걸 2진법으로 변환하고 n자리수보다 작은 것은 0으로 채우면 될것같다.

function sol01(n, arr1, arr2) {

    const arr2_1 = []
    const arr2_2 = []
    
    const arrSecret = []
    let secret

    for (let i = 0 ; i < n ; i++) {
        arr2_1.push(arr1[i].toString(2).padStart(n,"0"))
        arr2_2.push(arr2[i].toString(2).padStart(n,"0"))

        secret = ""

        for (let j = 0 ; j < n ; j ++) {
            if ( arr2_1[i][j] === '0' && arr2_2[i][j] === '0'){
                secret += " "
            } else {
                secret += "#"
            }
        }
        arrSecret.push(secret)
    }


    return arrSecret;
}

아래의 코드는 가독성을 포기한 대신 변수 할당을 없앴다.
과연 더 빨라질까 아니면 더 느려질까 궁금하다

function sol02(n, arr1, arr2) {

    const arrSecret = []
    let secret
    
    for (let i = 0 ; i < n ; i++) {       
        secret = ""
        
        for (let j = 0 ; j < n ; j ++) {
            if ( arr1[i].toString(2).padStart(n,"0")[j] === '0' && arr2[i].toString(2).padStart(n,"0")[j] === '0'){
                secret += " "
            } else {
                secret += "#"
            }
        }
        arrSecret.push(secret)
    }
    
    
    return arrSecret;
}

다른 사람의 풀이

function sol1(n, arr1, arr2) {
    let num1, num2, s;
    let answer = [];
    //manually turning decimals to binaries cos i can!
    for (let i=0; i<n; i++){
        num1 = arr1[i];
        num2 = arr2[i];
        s = '';
        for (let j=0; j<n; j++){
            s = (num1%2 + num2%2) ? '#'+s : ' '+s;
            num1 = Math.floor(num1/2);
            num2 = Math.floor(num2/2);
        }
        answer.push(s);
    }    
    return answer;
}

%2를 이용해서 오른쪽으로 1비트씩 움직이며 검사를한다.

그리고 내가 한 것처럼 0 = ' '을 앞에서 채워넣는 과정이 없다. 내 코드는 .padStart(n,"0")를 없애면 안된다. 2진수로 변환하면서 계산하는것과 만든다음에 계산하는 것의 차이같다.

var sol2=(n,a,b)=>a.map((a,i)=>(a|b[i]).toString(2).padStart(n,0).replace(/0/g,' ').replace(/1/g,'#'))

항상 있는 1줄짜리 코드이다. 아래와 같이 바꿀 수 있다.

function sol2(n, a, b) {
  return a.map((a, i) => (a | b[i]).toString(2).padStart(n, '0').replace(/0/g, ' ').replace(/1/g, '#'));
}

속도 비교

sol2가 너무 느려서 반복횟수를 1천만에서 10만으로 바꿨다...

시간복잡도는 모두 $O(n^2)$ 이기 때문에 아마도 sol2에 추가 연산과정이 너무 많아서 느린 듯 하다.

이진 변환 반복하기

어느 순간엔가 1뒤에 0만 붙는 모양이 나올 수 도있을 것같은데 구체적인 조건을 모르겠으니 그냥 정직하게 돌려야겠다...

나의 풀이

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

    let zero = 0
    let n = 0
    let x = s

    while (x !=='1' ){
        s = x
        x = ''
        for (let i = 0 ; i < s.length ; i++){
            if (s[i] === '1') {
                x+='1'
            } else {
                zero++
            }
        }
        x = x.length.toString(2)
        n++
    }

    answer = [n, zero]

    return answer
}

if (s[i] === '1') 부분의 1에 따옴표''를 안해서 계속 무한 루프에 빠졌었다.

다른 사람의 풀이

function sol1(s) {
    var answer = [0,0];
    while(s.length > 1) {
        answer[0]++;
        answer[1] += (s.match(/0/g)||[]).length;
        s = s.replace(/0/g, '').length.toString(2);
    }
    return answer;
}

정규식을 사용하여 0의 갯수를 나보다 예쁘게 셌다.

내 방식과 다른 사람의 방식을 합친것

function sol01(s) {
    var answer = [0,0];

    let x = s
    
    while (x !=='1' ){
        s = x
        x = ''
        for (let i = 0 ; i < s.length ; i++){
            if (s[i] === '1') {
                x+='1'
            } else {
                answer[1]++
            }
        }
        x = x.length.toString(2)
        answer[0]++
    }
    
    return answer
}

속도 비교

공부하며 느낀 점

배열에 값을 저장하고 불러오는 것이 더 느릴 것이라고 생각했는데 계속해서 아니라는 결론이 나오고 있다.
나의 환경이 특이하거나, 그때그때 연산하고 그것에 또다른 연산을 하는 것 보다는 이미 연산해둔 값을 가져오는 것이 더 빠른 것같다.
마찬가지로 시간 복잡도가 같다면 한번에 여러가지를 동시에 처리하는 쪽이 느린 것 같다.
정규식을 활용하는 경우, 예전에 푼 문제에서는 정규식이 더 빨랐으나 이번에는 더 느렸다.
이전의 것은 시간복잡도가 $O(N)$ 이었고 이번것은 $O(N^2)$ 이었다. 아마도 정규식이 문자열 전체를 보기 때문에 시간복잡도가 클 수 록 효율이 떨어지는 것같다.