문제 : primePassword

현재 비밀번호를 새 비밀번호로 변경하는데 필요한 최소동작의 수를 리턴

• 한번에 한개의 숫자만 변경 가능
• 4자리의 소수인 비밀번호로만 변경 가능

let output = primePassword(1033, 1033);
console.log(output); // --> 0

output = primePassword(3733, 8779);
console.log(output); // --> 3 (3733 -> 3739 -> 3779 -> 8779)

문제의 접근

경우의 수가 엄청나게 나온다. 그렇다면 당연하게도 DFS 혹은 BFS의 방식으로 접근하는게 맞겠지만, 잘 활용할 자신이 없어서 하나하나 차근차근 해결해 나가기로 했다.

우선 필요한 것은 변경된 숫자가 소수인지 확인해주기 위함 함수가 필요하다고 생각해서 그걸 먼저 저의해주었다.

const isPrime = (num) => {
    let cnt = 0
    for(let i = 1; i <= num; i++){
      if(num%i === 0){
        cnt++
      }
    }
    return cnt===2 ? true : false
  }

다음으로 필요한 것은 그 숫자가 이전 숫자랑 비교했을 때 한개의 숫자만 변경하였는가를 확인해주는 함수다.

const isOneChange = (num, befor) => {
    let sub = num - befor;
    if(sub < 10 && String(befor)[3] !== String(newPwd)[3]){
      return true
    }else if(sub < 100 && sub%10 === 0 && String(befor)[2] !== String(newPwd)[2]){ 
      return true
    }else if(sub < 1000 && sub%100 === 0 && String(befor)[1] !== String(newPwd)[1]){ 
      return true
    }else if(sub%1000 === 0 && String(befor)[0] !== String(newPwd)[0]){
      return true
    }
    return false
  }

벌써 코드가 엄청 복잡해지기 시작했다. 그래도 이는 함수일 뿐이니 활용만 해주면 된다. 우선이 함수들을 활용해서 가능한 수들을 배열에 담아준다.

let candidate = [];
  let befor = curPwd;

  while(curPwd <= newPwd){
    curPwd++;
    if(isPrime(curPwd) && isOneChange(curPwd, befor)){
      candidate.push(curPwd)
      befor = curPwd
    }
  }
// candidate = [ 3739, 3769, 3779, 5779, 6779, 8779 ]

이 함수를 통해서 만들어질 수 있는 모든 경우의 수가 배열에 담기게 된다. 그렇다면 이제 이 배열에서 차근차근 나아가면서 한자리씩 변경했을 때 새 비밀번호와 가까워질 수 있는 지를 확인해가며 변경 횟수를 헤아리면 된다고 생각했다.

// candidate = [ 3739, 3769, 3779, 5779, 6779, 8779 ]
// (3733 -> 3739 -> 3779 -> 8779) 이기 때문에 3769는 거칠 필요가 없다 때문에 3779의 값이
// 되기까지 는 1번만 변경하면 된다. 때문에 아래 확인이 필요해진다.

let change = new Array(4).fill(false) //바꾼걸 또 바꾸는 것인지 확인용
  let cnt = 0;
  let current = curPwd
  while(candidate.length > 0){
    let target = candidate.shift();
    for(let i = 0; i < change.length; i++){
      if(String(current)[i] !== String(target)[i]){
        if(!change[i]){
          cnt++
          change = new Array(4).fill(false);
          change[i] = true;
        }
        current = target
      }
    }
  }
  return cnt;

결과는 4/9의 통과율을 보여준다.
나머지 문제들은 조금의 수정만이 필요할줄 알았지만 전혀 다른 문제였다. 위 코드는 가장 중요한 사실 하나를 간과하고 있다.

비밀번호가 기존 수보다 낮아질 수도 있다.

때문에 일부는 통과가 가능할지라도 다른 숫자의 경우 절대 통과가 불가능하다.

거의 3시간을 고민했지만 절대 생각해낼 수 없을 거라 생각해 결국 정답지를 보았다...

const isPrime = (num) => {
  if (num % 2 === 0) return false;
  let sqrt = parseInt(Math.sqrt(num));
  for (let divider = 3; divider <= sqrt; divider += 2) {
    if (num % divider === 0) {
      return false;
    }
  }
  return true;
};

// 4자리 수를 받아서 각 자리수의 수들의 배열로 변환하는 함수
//  let output = splitNum(3359);
//  console.log(output); // --> [3, 3, 5, 9]
const splitNum = (num) => {
  const digits = num.toString().split('');
  return digits.map((d) => Number(d));
};

// 길이의 4의 수 배열을 받아서, 4자리의 수로 변환하는 함수
//  let output = splitNum([3, 3, 5, 9]);
//  console.log(output); // --> 3359
const joinDigits = (digits) => Number(digits.join(''));

const primePassword = (curPwd, newPwd) => {
  if (curPwd === newPwd) return 0;
  // bfs를 위해 queue를 선언
  let front = 0;
  let rear = 0;
  const queue = [];
  const isEmpty = (queue) => front === rear;
  const enQueue = (queue, item) => {
    queue.push(item);
    rear++;
  };
  const deQueue = (queue) => {
    return queue[front++];
    // const item = queue[front];
    // front++;
    // return item;
  };

  // 각 4자리의 방문 여부를 저장하는 배열
  // 한 번 방문한 수(가장 최소의 동작으로 만든 수)는 다시 방문할 필요가 없다.
  const isVisited = Array(10000).fill(false);
  isVisited[curPwd] = true;
  // bfs를 위한 시작점
  // 큐에는 [필요한 동작 수, 비밀번호]가 저장된다.
  enQueue(queue, [0, curPwd]);
  // bfs는 큐가 빌(empty) 때까지 탐색한다.
  while (isEmpty(queue) === false) {
    const [step, num] = deQueue(queue);
    // 각 자리수 마다 변경이 가능하므로 4번의 반복이 필요하다.
    for (let i = 0; i < 4; i++) {
      const digits = splitNum(num);
      // 0부터 9까지 시도한다.
      for (let d = 0; d < 10; d++) {
        // 각 자리수마다 원래 있던 수(digits[i])는 피해야 한다.
        if (d !== digits[i]) {
          // 현재 자리수의 수를 변경하고,
          digits[i] = d;
          // 변경한 후 4자리 수를 구한다.
          const next = joinDigits(digits);
          // 만약 이 수가 새 비밀번호와 같다면 리턴한다.
          // next는 deQueue된 num으로부터 1단계 다음에 도달한 수이다.
          if (next === newPwd) return step + 1;
          // 1,000보다 큰 소수여야 하고, 방문된 적이 없어야 한다.
          if (next > 1000 && isPrime(next) && isVisited[next] === false) {
            // 방문 여부를 표시하고,
            isVisited[next] = true;
            // 큐에 넣는다.
            enQueue(queue, [step + 1, next]);
          }
        }
      }
    }
  }

  // 큐가 빌 때까지, 즉 모든 경우의 수를 탐색할 때까지 리턴되지 않은 경우
  // 현재 비밀번호에서 새 비밀번호를 만들 수 없다.
  return -1;
};

문제를 통해 생각해 볼 것

BFS를 사용해야 하는 문제였다. 이 문제가 왜 BFS를 사용하는지는 알 것 같았지만, 정말 어떻게 활용해야할지를 몰랐다. 아직 갈 길이 너무 먼 것 같다. 그래도 코드를 차근차근 따라가니 이해가되니 다행인 것 같다. 이 문제는 그냥 코드 자체를 외워야 할 것 같다.