[알고리즘] 124 나라의 숫자

문제 설명

124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.

1. 124 나라에는 자연수만 존재합니다.
2. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.

예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.

10진법	124 나라	10진법	124 나라
1	1	6	14
2	2	7	21
3	4	8	22
4	11	9	24
5	12	10	41

자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.

제한사항

• n은 500,000,000이하의 자연수 입니다.

입출력

n	result
1	1
2	2
3	4
4	11

나의 풀이

let n = 10;

function solution(n) {
  let answer = "0";
  let Lang = ["1", "2", "4"];

  for (let i = 0; i < n; i++) {
    answer = (parseInt(answer) + 1).toString();

    for (let j = 1; j <= answer.length; j++) {
      let current = parseInt(answer[answer.length - j]);
      let prev = answer[answer.length - (j + 1)];

      if (current === 4) {
        answer = answer.replace(
          `${prev ? prev : ``}` + `${current}`,
          `${parseInt(prev ? prev : 0) + 1}` + `1`
        );
      }
    }
  }

  let result = "";

  for (let i = answer.length - 1; i >= 0; i--) {
    result = Lang[parseInt(answer[i] - 1)] + result;
  }

  return result;
}

const t0 = performance.now();
console.log(solution(n));
const t1 = performance.now();
console.log(t1 - t0, "milliseconds");

최초의 나의 풀이다. 

1부터 n까지 반복하면서 1씩 증가시키는 방법으로 작업하였다. 

 

하지만 500,000,000번 반복할 경우 작업 시간이 너무 오래걸리면서 코드 최적화가 필요하다고 느꼈다. 

let n = 500000000;
//  41 10
//  42 11
//  44 12
//  111 13
//  112 14
//  114 15
//  121 16
//  122 17
//  124 18
//  141 19
//  142 20
//  144 21
//  211 22
//  212 23
function solution(n) {
  const LANG = [1, 2, 4];

  let check = parseInt(n % 3 === 0 ? n / 3 : n / 3 + 1);

  let temp = n - (check - 1) * 3 - 1;
  let baseArray = [0];

  for (let i = 1; i < check; i++) {
    baseArray[0] += 1;

    for (let j = 0; j < baseArray.length; j++) {  -- 1
      if (baseArray[j] === 4) {
        if (baseArray[j + 1]) {
          baseArray[j + 1] += 1;
        } else {
          baseArray.push(1);
        }
        baseArray[j] = 1;
      }
    }
  }

  let result = "";

  baseArray.reverse();

  if (!(baseArray[0] === 0 && baseArray.length === 1)) {
    for (let i = 0; i < baseArray.length; i++) {
      result = result + LANG[baseArray[i] - 1];
    }
  }

  return result + LANG[temp];
}

const t0 = performance.now();
console.log(solution(n));
const t1 = performance.now();
console.log(t1 - t0, "milliseconds");
// for (let i = 1; i <= 25; i++) {
//   console.log(i, " = ", solution(i));
// }

그래서 이번에는 배열을 활용해서 값이 3보다 크면 다음으로 넘겨주는 방식으로 작업을 하였다. 

 

즉, baseArray의 첫 번째 인자에 우선 값을 계속 더해주고, 다음 인자로 넘어가서 다시 값을 확인해 4보다 크면 

또 다음 값으로 넘기는 방식이다. 

 

check, 앞자리가 3번씩 반복되는 특징을 이용해서 만들었지만 여전히 500,000,000번 실행할 경우 

시간이 오래걸리는 것을 확인했다. 

let n = 500000000;
//  41 10
//  42 11
//  44 12
//  111 13
//  112 14
//  114 15
//  121 16
//  122 17
//  124 18
//  141 19
//  142 20
//  144 21
//  211 22
//  212 23
function solution(n) {
  const LANG = [1, 2, 4];

  let check = parseInt(n % 3 === 0 ? n / 3 : n / 3 + 1);

  let temp = n - (check - 1) * 3 - 1;
  let baseArray = new Array(20).fill(0);
  baseArray[0] = check - 1;

  for (let i = 0; i < baseArray.length; i++) {
    while (baseArray[i] !== 0 && baseArray[i] - 3 > 0) {
      baseArray[i + 1]++;
      baseArray[i] = baseArray[i] - 3;
    }
  }

  baseArray = baseArray.filter((value) => value);

  baseArray.reverse();

  let result = "";

  if (!(baseArray[0] === 0 && baseArray.length === 1)) {
    for (let i = 0; i < baseArray.length; i++) {
      result = result + LANG[baseArray[i] - 1];
    }
  }

  return result + LANG[temp];
}
const t0 = performance.now();
console.log(solution(n));
const t1 = performance.now();
console.log(t1 - t0, "milliseconds");
// for (let i = 1; i <= 25; i++) {
//   console.log(i, " = ", solution(i));
// }

이번엔 처음부터 n의 값을 배열의 첫 번째 인자에 넣고 3씩 빼서 다음 인자에 + 1 시키는 방법으로 작업해보았다. 

 

500,000,000번 실행을 하면 265ms 정도 시간이 걸리는것을 확인했다. 

실행속도가 확실히 줄었지만, 여전히 오래 걸린다고 판단해 수정하였다. 

let n = 9;
//  41 10
//  42 11
//  44 12
//  111 13
//  112 14
//  114 15
//  121 16
//  122 17
//  124 18
//  141 19
//  142 20
//  144 21
//  211 22
//  212 23

// 1 2 3
// 1 2 10

// 12

// 1 2 0
// 1 2 4

// 001 1   1
// 002 2   2
// 010 3   0
// 011 4  11
// 012 5  12
// 020 6  10
// 021 7  21
// 022 8  22
// 100 9  20
// 101 10 01

//  10 => 3 => 1
//   1    0    1
//  10 => 3 => 0
//   9 => 2 => 0
function deep(n, a) {
  if (n === 0) return;
  a.push(n % 3);

  deep(parseInt((n - 1) / 3), a);
}

function solution(n) {
  var answer = "";

  const arr = [];
  deep(n, arr);

  const LANG = ["4", "1", "2"];

  for (let i = 0; i < arr.length; i++) {
    answer = LANG[arr[i]] + answer;
  }

  return answer;
}

const t0 = performance.now();
console.log(solution(n));
const t1 = performance.now();
console.log(t1 - t0, "milliseconds");
// for (let i = 1; i <= 25; i++) {
//   console.log(i, " = ", solution(i));

// }

3진수를 만드는 방식을 활용해 코드를 작업했다. 

 

10진수 1, 2, 3이 각각 3진수에서는 1, 2, 10이고 124 나라에서는 1, 2, 4이다. 

3진수에서 0, 1, 2를 4, 1, 2 순으로 생각한다면 

 

10진수 1, 2, 3이 1, 2, 0이 된다. 즉 3을 n으로 넣었을 때, 0이 배열에 들어가면 성공인 것이다. 

 

그러면 deep 함수에서는 n % 3 을 한 값을 배열에 넣어주고 재귀함수로 다시 deep 함수를 호출한다. 

 

처음 n 은 3이기 때문에 n %  3 ( 3 % 3 )은 0이 된다. 

우리가 목표로 하는 0이 배열에 들어갔기 때문에 다음 재귀함수에서 n을 0으로 만들어서 재귀함수를 탈출해야한다. 

그러므로 deep(n / 3, a) 일반적인 3진수 만드는 재귀함수에서 n - 1을 해주면 3 => 2가 되어 (n - 1) / 3은 0이 된다.

 

한 문제를 풀기위해서 하루라는 시간을 전부 사용해서 푼적은 처음이였다. 

알고리즘을 쉽게 생각했는데, 풀다보니 개발을 하는 폭을 넓혀주고, 자주 사용하지 않는 함수나 개발 방법을 사용하며, 

개발 능력도 증가하는 것 같다. 

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges