[프로그래머스] 비밀지도 - Javascript

devmin24·2021년 8월 6일
0

⏳ 도전! 알고리즘

목록 보기
28/32
post-thumbnail
post-custom-banner

문제 링크

문제

네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.

  • 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다.
  • 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
  • "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다.
    암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.
  • 네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.
    원래의 비밀지도를 해독하여 '#', 공백으로 구성된 문자열 배열로 출력하라.

입출력 예제

매개변수
n5
arr1[9, 20, 28, 18, 11]
arr2[30, 1, 21, 17, 28]
출력["#####","# # #", "### #", "# ##", "#####"]

매개변수
n6
arr1[46, 33, 33 ,22, 31, 50]
arr2[27 ,56, 19, 14, 14, 10]
출력["######", "### #", "## ##", " #### ", " #####", "### # "]

풀이

어휴, 문제가 길다. 하지만 그림과 입출력 예제를 보고 규칙만 잘 찾는다면 쉽게 이해할 수 있다.
문제에서 힌트를 주었다. 바로 이진수이다.

  • arr1, arr2 배열에 담긴 요소들을 이진수로 나타내고 같은 인덱스의 요소끼리 비교한다.(지도를 겹친다.)
  • 지도에는 공백(" ")과 벽("#")이 있는데, 공백은 0이라 하고, 벽은 1이라 한다.
  • 공백(=0)은 지도 1,2가 모두 공백이어야 공백이다.(AND연산)
  • 벽(=1)은 지도 1,2 중 어느 하나라도 벽이면 벽이다.(OR연산)
  • 0과 1을 (" ")과 ("#")로 바꾸어 출력한다.

10진수를 2진수로 변환하는 방법을 알아보자.

Number.prototype.toString(): 특정한 Number 객체를 나타내는 문자열을 반환한다. 매개변수로 수의 값을 나타내기 위해 사용되기 위한 기준을 정하는 2와 36사이의 정수를 담을수 있다. 더 알아보기
즉, toString(2)를 사용해 이진수로 문자열을 반환할 수 있다.

아래의 그림은 비트연산자의 설명이다. 이번 문제에서 벽("#")은 OR(|) 조건을 성립한다.

그럼 공백(" ")은 AND연산이잖아? 이라는 궁금증이 생길 것이다. 아래 그림을 보면 궁금증을 해결할 수 있다.

위의 그림을 보면 OR연산 하나로 공백(" ")과 벽("#")의 조건을 모두 성립하는 것을 볼 수 있다.

function solution(n, arr1, arr2) {
    var answer = [];
   
    for(let i=0; i<n; i++){
        // toString(2)은 이진수로 반환하는 것.
        const bin = (arr1[i] | arr2[i]).toString(2);
        // console.log(bin);
           let line = [];
        for(let j = bin.length-n; j<bin.length; j++) { // j가(인덱스값)이 -1일 경우 undefined 반환.
            if(bin[j] === '1') { // 1이면 '#', 그 외 ' '
                line.push('#');
            } else {
                line.push(' ');
            }
        }
        answer.push(line.join(''));
    }
    return answer;
}

코드를 풀이하자면,

  • 각 배열의 요소들을 n만큼(=arr.length) 돌며 이진수로 변환하여 OR연산 처리해준다.
  • 만약 9의 경우 이진수는 1001인데 n(=5)의 자릿수보다 부족하다. 이럴 땐, 예제 그림과 같이 01001로 만들어주어 처리해야한다.
    처리하는 방법에는 여러가지가 있다. padStart() 메서드를 사용하여 처리할 수도 있다. 하지만 나는 이러한 방법도 있다는 것만 숙지하도록 하고 다른 방법으로 풀어나갔다.

padStart():현재 문자열의 시작을 다른 문자열로 채워, 주어진 길이를 만족하는 새로운 문자열을 반환한다. 채워넣기는 대상 문자열의 시작(좌측)부터 적용된다. 더 알아보기

  • 자, 그럼 어떻게 풀어나갈까? 바로 두번째 for문에서 j = bin.length-n을 해주면 된다. 그 이유는 바로 뒤에 나오는 if문을 보면 알 수 있다.
    padStart()로 자릿수를 채우지 않고, bin.length-n을 하면 보통은 0이 된다. 예외적으로 9와 같은 네자리 이진수들은 -1이 될 것이다. 그리고 if문을 사용해 bin[j]가 1일 경우에만 "#"으로 변환해주고, 그 외 모든 것들은 " "으로 변환한다.
    참고로 bin[-1]undefined를 반환한다. 그러므로 else에 해당된다.
  • 그럼 이제 line[]에는 ["#"," ","#"," ","#"] 이런 형태로 담기게 될 것이다. 출력 형식에 맞춰주기 위해 join()메서드를 사용한다.

Array.prototype.join(): 배열의 모든 요소를 연결해 하나의 문자열로 만든다. 더 알아보기

  • ["# # #"]으로 출력되는 것을 볼 수 있다.

다른 사람의 풀이

다른 사람의 풀이로 공부를 하다가 정규표현식을 이용해 간단히 풀이한 것을 보고 새롭게 다가와 추가한다.

var solution=(n,arr1,arr2)=>arr1.map((a,i)=>(a|arr2[i]).toString(2).padStart(n,0).replace(/0/g,' ').replace(/1/g,'#'))
  • arr1을 map()을 돌려 a의 요소와 arr2 배열을 OR연산 해준다. 여기까진 내 풀이와 같다.
  • 아까 설명했던 padStart()메서드를 사용하여 n의 자릿수만큼 0으로 채운다.
  • 그리고 정규표현식으로 이용해 전역에서 0과 1을 찾아 replace()메서드를 이용하여 0은 " ", 1은 "#"로 변환한다.

String.prototype.replace(): 어떤 패턴에 일치하는 일부 또는 모든 부분이 교체된 새로운 문자열을 반환한다. 그 패턴은 문자열이나 정규식(RegExp)이 될 수 있으며, 교체 문자열은 문자열이나 모든 매치에 대해서 호출된 함수일 수 있다. 더 알아보기

개인적으로 내 풀이보다 위의 풀이가 더 직관적이고 맘에 든다. 내 풀이에선 1은 "#"으로 변환하고, 그 외는 모두 ' '으로 변환하게 하였는데 이것이 나중에 충분한 오류를 범할 수 있을 것이다. 또 나는 새로운 배열에 변환값을 담아 출력되는 answer 배열에 push하는 방식으로 풀었는데, 위의 풀이는 replace()메서드로 배열 자체의 요소를 변환해버린다.

Takeaway

이번 문제는 되게 고영양 문제였던 것 같다. 한 문제를 풀면서 배운 점이 되게 많았다. 이진수로 변환하는 법과 비트 연산자, 새로운 메서드들..
이진수를 변환하는 과정을 메서드를 사용하지 않고 코드로 풀어내는 풀이를 보았는데, 친절한 메서드를 사용하지 않는 것이 더 바람직하지 않다고 생각하여 메서드를 사용했다. 그래도 이진수를 코드로 풀어내는 과정에서 얻는 지식이 있었다!
또, 처음에 비트연산자를 사용하지 않고 조건문을 이용해 풀면 되겠다 생각했었는데, 이 문제의 출제 의도가 비트 연산자를 잘 다룰 수 있는지를 보는 것이였기 때문에 의도에 맞게 비트 연산자를 배워 사용했다. 비트 연산자 최고 👍

profile
꾸준함, 열정 한 가득 챙겨 끝없는 목표를 향해 달려가는 개발자👩‍💻
post-custom-banner

3개의 댓글

comment-user-thumbnail
2022년 1월 18일

설명이 좋네요 감사합니다!

답글 달기
comment-user-thumbnail
2022년 5월 9일

안녕하세요 잘 보고 갑니다 혹시 질문하나가 있는데..
let j = bin.length-n을 왜 하는지 이해가 안되는데
bin.length-n이 0이 된다면 0을 써도 될줄 알고 0을 써보니 일부의 케이스에선 통과를 하지 못해서 그런데 왜 그렇게 쓰는지 알수가 있을까요?

답글 달기
comment-user-thumbnail
2023년 7월 20일

덕분에 도움이 되었습니다!

답글 달기