83.md

배열 만들기 2

레벨 0인데 잘안풀린다...

처음에 접근은 규칙성을 찾으려고 노력하였다. 내가 찾은 규칙성은 이렇다

값	개수
	2^0
5		5 * 1
	2^1
50		5 * 10
55		5 * 11
	2^2
500		5 * 100
505		5 * 101
550		5 *110
555		5 * 111
	2^3
5000		5 * 1000
5005		5 * 1001
5050		5 * 1010
5055		5 * 1011
5500		5 * 1100
5505		5 * 1101
5550		5 * 1110
5555		5 * 1111

위 표를 보면 각 값들이 어떤 규칙성으로 가지고 만들어지고 총 개수가 어떻게 되는지를 알 수 있었다. 나는 여기서 0 과 1로 이루어진 숫자(세번째 칸)들을 만들어낼 수 있다면 이 숫자에 5를 곱하면 원하는 배열을 만들수 있었다. 그렇다면 각 자리수마다 앞의 1을 제외하고 0 과 1의 값을 가질 수 있다. 즉 이것은 중복수열인 것이다.

그런데 이것을 이렇게까지 풀어야하는 것인가 하는 의문이 들었다. 이 문제는 레벨 0이기때문에 좀 더 쉬운 방법이 있을거라는 생각이 있었고 그 방법은 다름아닌 Try1이였다.

Try1

사실 이 방법은 힌트를 통해서 알게 되었다. 시작점과 끝점을 주기때문에 그 안에 5와 0으로만 이루어진 숫자를 고르면 되는 것이였다. 굳이 이전처럼 규칙성을 찾을 필요가 없었다.

function solution(l, r) {
  const result = [];
  for (let i = l; i <= r; i++) {
    if (!String(i).match(/[12346789]/g)) result.push(i);
  }
  return result.length === 0 ? [-1] : result;
}

Try2

이제 위에서 언급한 1과 0으로 이루어진 배열들을 어떻게 만들수 있을까 에 대한 로직 구현은 어떻게 해야할까? 사실 이 부분에 대한 코드는 약간 구체적이지 못했으나, 다른 사람의 코드를 보고 감을 잡을 수 있었다.

function solution(l, r) {
  const result = [];
  let i = 1;

  while (true) {
    const tmp = Number(i.toString(2)) * 5; // i에 대한 이진수 변환수 * 5
    i++;

    if (l > tmp) continue;
    if (tmp > r) break;

    result.push(tmp);
  }

  return result.length === 0 ? [-1] : result;
}

참고

가장 복잡한 방법으로 풀어보는 것은 바로 중복순열를 이용하는 방법이 아닐까하는 생각이 든다. 나중에 복습겸 중복순열을 통해서 구현해보자. 조합, 순열 등의 기본적인 로직은 자주 복습해주는 것이 좋은 것 같다. (특히 나는 자주 까먹..., 저런 로직은 약간 공식같은 느낌이라서...)