배열 만들기 2

배열 만들기 2

문제 자체도 흥미롭지만 그보다 궁여지책으로 자바스크립트 제네레이터를 사용해서 푼 문제이기에 가져왔다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/181921

문제 설명

정수 l과 r이 주어졌을 때, l 이상 r이하의 정수 중에서 숫자 “0”과 “5”로만 이루어진 모든 정수를 오름차순으로 저장한 배열을 return 하는 solution 함수를 완성해 주세요.

만약 그러한 정수가 없다면, -1이 담긴 배열을 return 합니다.

입출력 예

l	r	result
5	555	[5, 50, 55, 500, 505, 550, 555]
10	20	[-1]

풀이

숫자 5로 현혹시켜놨지만 사실 이건 이진수 문제다. 쉽게 말해 5, 50, 55, 500, 505 … 는 그냥 1, 10, 11, 100, 101 인 이진수에서 1을 5로 바꾼 것 뿐이다. 따라서

1. 숫자를 이진수로 출력하고
2. 출력한 이진수를 강제로 십진수로 인식시켜 다시 숫자로 만든 뒤
3. 그 숫자에 5를 곱한다

이렇게 하면 문제가 간단히 풀린다. 그런데 문제는 l 과 r의 범위이다. 산수를 더럽게 못해서 😂 이진수 숫자를 얼마까지 만들어야 되는지 모르겠던 것이다.

사실 입력받은 숫자를 각 자리수별로 분해해서 5로 나눈 뒤 그걸 이진수로 인식시켜 숫자로 바꾸는 방법을 사용할 수 있다. 하지만 귀찮다.

그래서 수열 자체는 무한히 나오게 조치하고, 수열이 l ~ r 범위 내에 들어갈 때까지 제네레이터를 열심히 굴린 뒤에(사실 그다지 열심히도 아니다. 이진수는 자릿수가 빠르게 증가한다) 범위를 빠져나갈 때까지 수열을 뽑아오는 방법을 고안해보았다.

아래가 그 해답이다.

function* gen50() {
  let i = 1;

  while (true) {
    yield Number(Number(i).toString(2)) * 5;
    i++;
  }
}
function solution(l, r) {
  const n = gen50();
  let a = 0;
  const arr = [];

  while (a < l) {
    a = n.next().value;
  }
  while (a <= r) {
    arr.push(a);
    a = n.next().value;
  }

  return arr.length ? arr : [-1];
}

자바스크립트 제네레이터에 대해서는 Javascript generator를 참고하기 바란다.

Number(i).toString(2)는 숫자를 이진수 “문자열” 로 출력한다. 그걸 그대로 Number()에 넣었으니, 자바스크립트 인터프리터는 들어온 문자열을 십진수로 착각한다. 그러니까 고의로 착각을 “유도”한 것이다. 그 상태에서 5를 곱하면 원하는 505 수열이 만들어진다. 이게 제네레이터의 핵심 로직이다.

아래 solution() 함수에서는 이 제네레이터를 사용하여, 앞자르기 동작 후 필요한 만큼의 수열을 뽑아다 배열에 넣고 그 값을 리턴하게 되어 있다. 설명의 여지 없이 깔끔하다.

여기에 Lodash라이브러리까지 개입하면 _.dropWhie()과 _.takeWhile() 까지 끼얹어서 더 직관적인 로직을 짤 수도 있을 것이다. 하지만 코드 양은 줄지 않고 오히려 늘어나니까 이것까지 하진 않겠다. 어차피 코딩테스트에서 외부 라이브러리를 가져다 쓸 수도 없다 😘