알고리즘 눈덩이 ⛄️

🧑‍🏫 문제

다음의 조건을 만족하면서 현재의 비밀번호('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)

🖋️ Pseudocode (수도코드)

1. 소수를 판별하는 함수를 만든다 (isPrime)
2. 전달받은 숫자를 각각의 배열요소로 분리하는 함수를 만든다 (splitNum)
3. 전달받은 배열의 각각의 요소를 하나로 함치는 함수를 만든다 (joinDigits)
4. 전달받은 curPwd를 newPwd로 바꿀때 몇 번의 작업을 해줘야하는지 찾는 함수를 만든다 (4자리 숫자를 받고 한번에 하나씩만 숫자를 변경할 수 있음)
   4-1. front rear구조의 queue를 생성한다
   4-2. queue가 비어있을때를 판별하는 isEmpty함수를 만든다
   4-3. enQueue(rear + 1)와 deQueue(front + 1)를 만든다
   4-4. bfs는 중복탐색 노드를 제외해야 하기 때문에 탐색된 노드는 isVisited로 관리해준다
   4-5. bfs탐색을 위한 시작점을 만들어준다 (입력받은 curPwd를 탐색시작점으로 잡을 것이다)
   4-6. bfs를 구현한다
   4-6-1. queue가 비어있지 않을 때 계속해서 반복하는 while문을 만든다 (isEmpty(queue) === false)
   4-6-2. 4-5에서 enQueue했던 bfs의 시작점을 deQueue해서 [변경횟수, 숫자]로 구조분해할당한다
   4-6-3. 입력받은 숫자의 자릿수를 변경하는 i의 반복문을 만들어준다
   4-6-4. 4-6-2에서 deQueue를 통해 구조분해할당받았던 4자리 숫자를 2의 splitNum을 통해 각각의 배열 요소로 분해한다
   4-6-3-1. 입력받은 숫자의 자릿수에 해당하는 숫자를 0~9로 순회하는 d의 반복문을 만들어준다
   4-6-3-2. d를 0~9의 숫자로 바꿔가며 우리가 찾고자하는 newPwd가 있는지 찾는다
   4-6-3-2-1. d가 순회되며 찾은 숫자가 우리가 찾는 newPwd일 경우 4-6-2에서 구조분해할당 받은 변경횟수(step)를 +1 해주고 return한다 이때 우리가 원하는 값을 찾았음으로 반복문은 모두 끝난다
   4-6-3-2-2. d가 순회되며 숫자를 찾았는데 우리가 찾는 newPwd가 아니지만 1000이상의 방문한적 없는(isVisited[next] === false) 소수의 숫자면 queue에 넣어준다(변경횟수 + 1)
5. 찾는 값이 없으면 -1을 return한다

👾 Code

// <1. 소수를 판별하는 함수를 만든다 (isPrime)>
const isPrime = (num) => {
    if (num % 2 === 0) return false;
    let sqrt = parseInt(Math.sqrt(num)); //sqrt ???
    for (let divider = 3; divider <= sqrt; divider += 2) {
      if (num % divider === 0) {
        return false;
      }
    }
    return true;
  };
  
  // <2. 전달받은 숫자를 각각의 배열요소로 분리하는 함수를 만든다 (splitNum)>
  //  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));
  };
  
  // <3. 전달받은 배열의 각각의 요소를 하나로 함치는 함수를 만든다 (joinDigits)>
  //  let output = splitNum([3, 3, 5, 9]);
  //  console.log(output); // --> 3359
  const joinDigits = (digits) => Number(digits.join(''));
  
  // <4. 전달받은 curPwd를 newPwd로 바꿀때 몇 번의 작업을 해줘야하는지 찾는 함수를 만든다 (4자리 숫자를 받고 한번에 하나씩만 숫자를 변경할 수 있음)>
  const primePassword = (curPwd, newPwd) => {
    if (curPwd === newPwd) return 0; // 입력받은 값과 찾고자하는 값이 같으면 0을 return해준다.

    // <4-1. front rear구조의 queue를 생성한다>
    let front = 0;
    let rear = 0;
    const queue = [];

    // <4-2. queue가 비어있을때를 판별하는 isEmpty함수를 만든다>
    const isEmpty = (queue) => front === rear;

    // <4-3. enQueue(rear + 1)와 deQueue(front + 1)를 만든다>
    const enQueue = (queue, item) => { // enqueue 함수에는 [필요한 동작 수, 비밀번호]로 이뤄진 item 인자를 queue에 넣어준다.
      queue.push(item);
      rear++;
    };
    const deQueue = (queue) => {
      const item = queue[front];
      front++;
      return item;
      //return queue[front++]; 위의 세줄은 해당 줄과 같은 동작을 함
    };

    // <4-4. bfs는 중복탐색 노드를 제외해야 하기 때문에 탐색된 노드는 isVisited로 관리해준다>
    // 각 4자리의 방문 여부를 저장하는 배열 bfs탐색을 진행할 때 한번 방문한 노드는 다시 방문할 이유가 없기 때문에 만듬
    const isVisited = Array(10000).fill(false);
    isVisited[curPwd] = true;

    // < 4-5. bfs탐색을 위한 시작점을 만들어준다 (입력받은 curPwd를 탐색시작점으로 잡을 것이다)>
    // 팔요한 동작 수는 0, 비밀번호는 primePassword에서 입력받은 curPwd로 해준다.
    enQueue(queue, [0, curPwd]);
    


    // <4-6. bfs를 구현한다>
    // <4-6-1. queue가 비어있지 않을 때 계속해서 반복하는 while문을 만든다 (isEmpty(queue) === false)>
    while (isEmpty(queue) === false) {

      // <4-6-2. 4-5에서 enQueue했던 bfs의 시작점을 deQueue해서 [변경횟수, 숫자]로 구조분해할당한다> 
      const [step, num] = deQueue(queue); //[변경횟수 = step, 숫자 = num]

      // <4-6-3. 입력받은 숫자의 자릿수를 변경하는 i의 반복문을 만들어준다>
      for (let i = 0; i < 4; i++) {

        // <4-6-4. 4-6-2에서 deQueue를 통해 구조분해할당받았던 4자리 숫자를 2의 splitNum을 통해 각각의 배열 요소로 분해한다>
        const digits = splitNum(num);

        // <4-6-3-1. 입력받은 숫자의 자릿수에 해당하는 숫자를 0~9로 순회하는 d의 반복문을 만들어준다>
        for (let d = 0; d < 10; d++) { // 각 자리의 수를 본인 수 제외하고(d !== digits[i]) 모두 바꿔본다 0-9까지.
          if (d !== digits[i]) { 

            // 현재 자리수의 수를 변경하고,
            digits[i] = d;

            // 자리수를 변경한 후의 4자리 수를 합쳐준다.
            const next = joinDigits(digits);
            
            // <4-6-3-2. d를 0~9의 숫자로 바꿔가며 우리가 찾고자하는 newPwd가 있는지 찾는다>
            // 우리는 여기서 자리수를 변경한 후의 4자리 수가 우리가 찾던 newPwd일 수도 있고 아닐 수도 있다 분기처리를 해주자.
            
            // <4-6-3-2-1. d가 순회되며 찾은 숫자가 우리가 찾는 newPwd일 경우 4-6-2에서 구조분해할당 받은 변경횟수(step)를 +1 해주고 return한다 이때 우리가 원하는 값을 찾았음으로 반복문은 모두 끝난다>
            if (next === newPwd) return step + 1;

            // <4-6-3-2-2. d가 순회되며 숫자를 찾았는데 우리가 찾는 newPwd가 아니지만 1000이상의 방문한적 없는(isVisited[next] === false) 소수의 숫자면 queue에 넣어준다(변경횟수 + 1)>
            if (next > 1000 && isPrime(next) && isVisited[next] === false) {

              // 방문 여부를 표시하고,
              isVisited[next] = true;

              // 큐에 넣는다.
              enQueue(queue, [step + 1, next]);
            }
          }
        }
      }
    }
    // 큐가 빌 때까지, 즉 모든 경우의 수를 탐색할 때까지 리턴되지 않은 경우
    // 현재 비밀번호에서 새 비밀번호를 만들 수 없다.
    return -1;
  };

Reference 1
Reference 2