[Algorithm] 프로그래머스 비밀지도 문제 풀이

글 수정사항은 노션 페이지에 가장 빠르게 반영됩니다. 링크를 참고해 주세요

 

2018년 카카오 블라인드 테스트 1차 비밀지도 문제(문제 번호 17681). 파라미터는 arr1 arr2 n 이렇게 3개를 받으며, n은 한 변의 길이를 나타낸다(배열 각 요소를 이진수로 변환한 후의 length).

 

❶ 2개의 배열을 받아

[9, 20, 28, 18, 11]; // arr1
[30, 1, 21, 17, 28]; // arr2

 

❷ 배열의 각 요소를 2진수로 변환한 뒤 (10진수 → 2진수 변환은 노트 참고)

['01001', '10100', '11100', '10010', '01011']; // arr1
['11110', '00001', '10101', '10001', '11100']; // arr2

 

❸ 0 → ' ' 공백, 1 → # 으로 변환

[' #  #', '# #  ', '###  ', '#  # ', ' # ##']; // arr1
['#### ', '    #', '# # #', '#   #', '###  ']; // arr2

 

❹ 각 배열 병합. arr1[i][j]와 arr2[i][j]를 비교할 때 둘 중 하나라도 #이면 그대로 # 사용

// arr1, arr2 첫번째 요소 비교
' #  #'
'#### '
-------
'#####'

 

결과 ▼

["#####","# # #", "### #", "# ##", "#####"];

 

❺ 해결 방식을 그림으로 표현하면 아래와 같다

 

내가 푼 방식

---

map, reduce를 이용해서 원시적으로 풀었다.

 

❶ 배열 각 요소를 2진수로 변환

const convertToBinary = (arr) => {
  return arr.reduce((acc, cur) => {
    let converted = cur.toString(2);
    converted = '0'.repeat(n - converted.length) + converted;
    return acc.concat(converted);
  }, []);
};

const map1 = convertToBinary(arr1);
const map2 = convertToBinary(arr2);

 

일부 숫자는 이진수 변환 후의 length가 n보다 작기 때문에 repeat() 메서드로 자릿수를 맞춰준다.

// length(자릿수)가 맞지 않기 때문에 두 이진수를 비교하기 애매하다
'1001'; // 숫자 9 이진수(arr1[0][0])
'11110'; // 숫자 30 이진수(arr2[0][0])

// repeat 메서드를 사용해 숫자 9 이진수의 부족한 자릿수만큼 '0' 추가
// n은 5라고 가정
'0'.repeat(n - '1001'.length) + '1001'; // '01001'

 

❷ 0 → ' ' 공백, 1 → # 으로 변환 — 이 부분은 OR 비트 연산자로 깔끔하게 풀 수 있다

return map1.map((el, i1) =>
  el
    .split('')
    .reduce(
      (acc, cur, i2) =>
        cur === '1' || map2[i1][i2] === '1' ? acc + '#' : acc + ' ',
      '',
    ),
);

 

레퍼런스 코드 분석

---

Bitwise Operator - Javascript Basic & Detail

 

비트 연산자

💡 비트는 이진(Binary) 숫자만 사용한다. 비트 연산자는 비트 수준에서 변수와 상호 작용하는 방법이다. 비트 수준에서의 평가는 일반 논리연산자보다 속도가 빠르다.

 

좋아요를 가장 많이 받은 다른 사람 코드를 보니 정말 깔끔하다. v | arr2[i] 요 코드는 단순히 OR 연산자를 사용한지 알았는데 자세히 보니 Vertical Bar |가 하나밖에 없다. 찾아보니 비트연산자의 OR이다.

function solution2(n, arr1, arr2) {
  return arr1.map((v, i) =>
    addZero(n, (v | arr2[i]).toString(2)).replace(/1|0/g, (a) =>
      +a ? '#' : ' ',
    ),
  );
}

const addZero = (n, s) => {
  return '0'.repeat(n - s.length) + s;
};

 

비트 연산자의 |(OR)은 || 논리 연산자와 비슷하다. 비교하는 비트가 0과 1이라면 1을 반환한다. 문제에서 요구하는 로직(비교하는 값이 0 혹은 1이면 1 반환)에 OR 비트 연산자를 적용하면 정확히 맞아떨어진다.

console.log(46 | 27); // 63

46의 2진수는 101110, 27의 2진수는 11011
101110 (46)
011011 (27)
------
111111 (63)

 

str.replace / 정규식

str.replace(regexp|substr, newSubstr|function)

 

replace() 메서드의 첫번째 인자엔 정규식도 올 수 있다. 두번째 인자엔 일치하는 요소에 어떤 로직을 수행할지에 대한 콜백을 넘길 수 있다.

'01001'.replace(/0|1/g, '*'); // '*****'
'01001'.replace(/0|1/g, (n) => (Number(n) ? ' ' : '#')); // '# ## '
// 0은 false로 평가되므로 ' ' 빈문자열 반환, 그 외엔 '#' 반환

 

참고로 정규식에서 | 교체구문은 OR 연산자와 동일하다.

const re = /0|1/;
'01001'.match(re); // ['0', index: 0, input: '01001', groups: undefined]

 

정규식에서 g(전역검색) 플래그를 사용하면 패턴과 일치하는 모든 내용을 찾는다. g 플래그가 없으면 패턴과 일치하는 첫번째 결과만 반환한다.

const re = /0|1/g;
'01001'.match(re); // ['0', '1', '0', '0', '1']

 

코드 풀이

❶ arr1 요소 순회

 

❷ arr1[i] arr2[i]에 OR 비트 연산자 적용

// arr1[i]는 14, arr2[i]는 22로 가정
14 | 22; // 30

/*
01110 (14)
10110 (22)
-----
11110 (30)
*/

 

❸ 이진수 변환

(30).toString(2); // '11110'

 

❹ 부족한 자리수에 '0'추가

const addZero = (n, s) => '0'.repeat(n - s.length) + s;

// n은 6(이라고 가정), s는 '11110'
addZero(6, '11110'); // '011110'

 

❺ 0 → ' ', 1 → # 으로 변환

'011110'.replace(/1|0/g, (n) => (+n ? '#' : ' ')); // ' #### '
// +'0' 형태로 작성하면 숫자로 형변환. Number('0')과 동일