들어가며

이 포스팅에서는 leetcode 추천 문제 top 75를 자바스크립트로 풀어보며 자바스크립트 공부와 알고리즘 공부를 동시에 합니다. 문제와 풀이를 적을 건데, 틀린 부분이나 더욱 개선될 부분이 있다면 댓글로 달아주시면 정말 감사하겠습니다.

번외편

이번에는 번외적으로 leetcode 추천 문제 75선이 아닌 카카오 신입 공채 문제였던 문제 하나를 풀이해보겠습니다.

문제

비밀 지도

문제 설명

문제 개요

Screen Shot 2019-11-03 at 9.07.57 PM.png

Screen Shot 2019-11-03 at 9.08.24 PM.png

예제

Screen Shot 2019-11-03 at 9.08.31 PM.png

풀이 과정

일단 코딩테스트 문제인만큼 빠르게 푸는데 초점을 두었습니다.

문제를 간단히 요약해보자면,

  1. 10진수를 2진수로 바꾸기
  2. OR연산을 하기
  3. 1은 #으로 0은 공백으로 치환하기
String.prototype.replaceAll = function(search, replacement) {
  var target = this;
  return target.replace(new RegExp(search, "g"), replacement);
};

function transSecretMap(n, arr1, arr2) { // 비밀 지도를 해석하는 함수
  return dec2Bin(n, orBinArr(dec2Bin(n, arr1), dec2Bin(n, arr2))).map(bin =>
    bin
      .toString()
      .replaceAll("1", "#")
      .replaceAll("0", " ")
  );
}

function dec2Bin(n, arr) { // 10진수(decimal)를 2진수(binary)로 바꿔주는 함수
  return arr.map(num => ("0".repeat(n) + num.toString(2)).slice(-n));
}

function orBinArr(arr1, arr2) { // 배열에 들은 2진수 숫자를 OR연산 하여 반환하는 함수
  return arr1.map((bin, idx) => parseInt(bin, 2) | parseInt(arr2[idx], 2));
}

console.log(transSecretMap(5, [9, 20, 28, 18, 11], [30, 1, 21, 17, 28]));
console.log(
  transSecretMap(6, [46, 33, 33, 22, 31, 50], [27, 56, 19, 14, 14, 10])
);

함수에 대한 설명은 각 주석을 보시면 될 것 같습니다.

배열을 활용하는 문제인만큼 소스코드가 복잡해지고 길어지지 않게 map 메소드를 적극활용하여 풀었습니다.

대략적인 프로세스는 아까 위에 말했던

  1. 10진수를 2진수로 바꾸기
  2. OR연산을 하기
  3. 1은 #으로 0은 공백으로 치환하기

이 순서를 따른다고 생각하시면 편합니다.

다만 이렇게 문제를 풀다보면 몇가지 자잘한 문제들이 생기는데요.

  1. 패딩 처리

이를테면, 1은 toString(2) 메소드를 이용하여 2진수로 변환하면 그냥 "1"이 되고, 2는 toString(2) 메소드를 이용하여 변환하면 "10"이 됩니다. 각각에 대해 1은 #으로 0은 공백으로 치환하면 "1" 은 "#" 이 되고, "10"은 "# "이 됩니다. 근데, 정답으로 제출되어야 하는 문자열은 특정 자릿수에 맞춘 문자열이 되어야 합니다. 이를테면 배열의 총 길이가 5일 때는 "ㅤㅤㅤㅤ#", "ㅤㅤㅤ#ㅤ"이 정답으로 제출되어야 합니다.

그 문제를 해결하기 위해 2진수로 변환하는 과정에서 기존의 문자열 앞에 "0".repeat(n)을 더해주고 그 이후에 slice(-n)이라는 문자열을 자르는 메소드를 이용하여 알맞게 필요한 부분을 잘라줬습니다. slice메소드에 -n의 인자를 주면 문자열의 끝에서부터 n번째 글자까지 가져옵니다.

이렇게 하면 패딩 처리에 관한 문제가 해결됩니다.

  1. 자바스크립트 String의 기본 메소드에 모든 문자열을 replace하는 메소드(일반적으로 replaceAll)가 존재하지 않는다.

이 문제에 대해서는 맨 위 소스의 내용을 보시면 되는데, 자바스크립트에서 String의 static 메소드로 replaceAll(해당하는 모든 문자열을 치환하는 함수)을 지원하지 않아서 직접 프로토타입체인에 replaceAll이라는 메소드를 만들어 추가해주는 부분입니다.

정규표현식 객체를 지원하기 때문에, new RegExp(search, "g")라는 객체를 만들어 해결합니다. search에는 우리가 검색하고 싶은 문자열을 넣어주면 됩니다.

bin.toString().replaceAll("1", "#").replaceAll("0", " ")

전체 소스 중 위 부분에서 replaceAll 메소드를 활용해주었습니다.

이렇게 2가지 에로사항을 잘 해결하시면 별다른 문제 없이 문제가 잘 풀리게 됩니다.

배운점

자바스크립트에 replaceAll이 기본 메소드로 존재하지 않는다.
자바스크립트에서 RegExp라는 객체를 제공하고, replace와 사용이 용이하다.
문자열.repeat(n)은 문자열을 n번 반복한 문자열이 리턴된다.
숫자.toString(진법) 메소드는 숫자를 특정 진법의 숫자 문자열로 바꿔준다.
parseInt(2진수, 2) 와 &, |등의 기호를 이용하여 bit연산이 가능하다.
slice(-n)으로 문자열의 끝에서부터 문자열을 짜르는 것이 가능하다.