Toy 문제 15

문제

다음의 조건을 만족하면서 현재의 비밀번호('curPwd')를 새 비밀번호(newPwd)로 변경하는 데 필요한 최소 동작의 수를 리턴해야 합니다.

• 한 번에 한 개의 숫자만 변경가능하다.
• 4자리의 소수(prime)인 비밀번호로만 변경가능하다.

정리하면, 비밀번호가 계속 소수를 유지하도록 숫자 한 개씩을 바꿔갈 때 현재 비밀번호에서 새 비밀번호로 바꾸는 데 최소 몇 개의 숫자를 변경해야 하는지를 리턴해야 합니다.

주의사항

• 4자리인 소수는 1,000 이상의 소수를 말합니다.(0011, 0997 등은 제외)

입출력 예시

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

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

 

수도코드(해석)

1. 소수를 판별하는 함수

2. 4자리 수를 배열로 변환하는 함수

3. 길이의 4의 배열을 받아서, 4자리의 수로 변환하는 함수

우선 위 조건을 만족하는 기본적인 함수들을 만들고

 

 

BFS를 사용합니다. 이유는 데이터의 깊이가 존재하지 않고, 전체적으로 탐색을 하면서 한번 하였으면 다시 돌아가지 않기위해 true false로 나타내기 때문입니다.

 

각 자리 마다 숫자를 바꿔줄수 있으니 반복문을 사용해서 바꿔줍니다.

이 때 조건을 현재 쓰고있는 숫자, 그리고 탐색을 했던숫자, 소수인 숫자일 때 조건을 만족하면 카운트를 해주고.

이 때 바꾸고자 하는 비밀번호랑 값이 같지 않을경우 큐에 값을 넣어주어서 다시 검사를 할 수 있도록 합니다.

 

BFS를 쓰는 가장 큰 이유는

각 자리중에 한자리를 바꾸어 소수를 바꾸어줄때 1개의 경우의 수가 생기지 않고 여러개의 숫자가 나오게 되는데 그 때마다 또 하나의 경우의 수를 추가해주는 방식이여서 DFS 같은 성질이라고 순간 착각 할 수 있지만, 비밀번호를 바꾸어 줄 때 생기는 가장 짧은 (최단거리)를 구하는 것이기 때문에 BFS가 맞고 이부분을 구현 할 때 코드를 어떻게 작성할지 생각이 안나서 까다로웠습니다.

 

꼭 숫자가 작은순부터 큰 순서대로 구할 필요가 없기 때문에 기존 값 보다 커졌다 작아졌다 할 수 있는 부분 있기 때문에 이러한 방식이 효율적입니다.

 

그리고 디버깅을 하면서 알아볼 때 소수판별식에서 너무 시간이 오래걸려 디버깅 잘하는 법이 있나 찾아봐야겠습니다..

코드

코드의 원리와 크게 어려운 부분은 한번에 길을 찾는 방식을 구현하는게 어려웠지만, 크게 없지만 자잘한 조건들이 많아서 코드의 복잡성이 있습니다.

좀 더 보기좋게 코드를 줄일 수 없을까 라는 고민을 하면서 다시 풀어봐야겠습니다.

 

// 소수 판별 함수
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자리 수를 받아서 각 자리수의 수들의 배열로 변환하는 함수
const splitNum = (num) => {
  const digits = num.toString().split('');
  return digits.map((d) => Number(d));
};

// 길이의 4의 수 배열을 받아서, 4자리의 수로 변환하는 함수
const joinDigits = (digits) => Number(digits.join(''));


// 비밀번호 변경 함수
const primePassword = (curPwd, newPwd) => {
  if (curPwd === newPwd) return 0; // 현재와 변경 하고자 하는 비밀번호가 같으면 바로 0리턴
  
  const queue = [];// bfs를 위해 queue를 선언
  let front = 0;
  let rear = 0;
 
  const isEmpty = (queue) => front === rear;

  const enQueue = (queue, item) => {
    queue.push(item);
    rear++;
  };
  const deQueue = (queue) => {
    return queue[front++];
  };

  const isVisited = Array(10000).fill(false);// 각 4자리의 방문 여부를 저장하는 배열, 한 번 방문한 수(가장 최소의 동작으로 만든 수)는 다시 방문할 필요가 없다.
  isVisited[curPwd] = true; 
  enQueue(queue, [0, curPwd]); //bfs를 위한 시작점 큐에는 [필요한 동작 수, 비밀번호]가 저장된다.
  while (isEmpty(queue) === false) {// bfs는 큐가 빌(empty) 때까지 탐색한다.
    const [step, num] = deQueue(queue); 
    for (let i = 0; i < 4; i++) {// 각 자리수 마다 변경이 가능하므로 4번의 반복이 필요하다.
      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;
};