[프로그래머스, 자바스크립트] 알고리즘-38 비밀지도

출처 : 프로그래머스 알고리즘 코딩테스트 Level.1

https://programmers.co.kr/learn/courses/30/lessons/17681?language=javascript

비밀지도

문제

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

지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 공백(" ) 또는벽(#") 두 종류로 이루어져 있다.
전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다.
각각 지도 1과 지도 2라고 하자.
지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다.
지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
지도 1과 지도 2는 각각 정수 배열로 암호화되어 있다.
암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.

입력 형식

입력으로 지도의 한 변 크기 n 과 2개의 정수 배열 arr1, arr2가 들어온다.
1 ≦ n ≦ 16
arr1, arr2는 길이 n인 정수 배열로 주어진다.
정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n 이하이다.
즉, 0 ≦ x ≦ 2n - 1을 만족한다.

출력 형식

원래의 비밀지도를 해독하여 '#', 공백으로 구성된 문자열 배열로 출력하라.

제한조건

1. 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
2. stages의 길이는 1 이상 200,000 이하이다.
3. stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.

• 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
• 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.

1. 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
2. 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

입출력 예시

n	arr1	arr2	result
5	[9, 20, 28, 18, 11]	[30, 1, 21, 17, 28]	["#####","# # #", "### #", "# ##", "#####"]
6	[46, 33, 33 ,22, 31, 50]	[27 ,56, 19, 14, 14, 10]	["######", "### #", "## ##", " #### ", " #####", "### # "]

 

풀이 과정

1. 주어진 숫자 배열을 이진수로 변환한다.
2. 변환된 이진수를 #과 공백으로 변환하여 저장한다.
3. #과 공백으로 변환된 배열 두개를 비교하여 복호화한다.

 

답안 (자바스크립트)

function solution(n, arr1, arr2) {
  let result1 = getBinaryArr(arr1);
  let result2 = getBinaryArr(arr2);

  return decrypt(result1, result2, n);

  // #과 공백으로 구성된 배열 반환
  function getBinaryArr(arr) {
    let result = [];
    for (let a of arr) {
      let s = "";
      for (let i = n; i > 0; i -= 1) {
        let pow = Math.pow(2, i - 1);
        if (a > pow) {
          a -= pow;
          s += "#";
        } else if (a === pow) {
          s += "#" + " ".repeat(i - 1);
          break;
        } else {
          s += " ";
        }
      }
      result.push(s);
    }
    return result;
  }

  // 복호화
  function decrypt(a, b, n) {
    let result = [];
    for (let i = 0; i < n; i += 1) {
      result[i] = "";
      for (let j = 0; j < n; j += 1) {
        result[i] += a[i][j] === "#" ? a[i][j] : b[i][j];
      }
    }
    return result;
  }
}

 

암호화의 작업이 두 번 필요하기 때문에 함수화하여 처리하였다.
한 번의 반복문에서 둘 다 처리도 가능하지만 지금의 코드도 가독성이라는 점에서는 만족스럽다.