Algorithm problem-15

1. 문제

• 현재 비밀번호와 새로운 비밀번호를 전달
• 4자리 새 비밀번호로 변경하는데 몇 번 바꿔야 하는지를 리턴
• 4자리 소수여야 하고, 1자리씩 변경
• 변경하는 동안에도 소수를 유지하여야 함

2. 시도

• 우선은 소수인지를 판별해 줄 내부 함수를 구현함
• 현재와 새 비밀번호가 같다면 0번이니 0을 리턴
• 1자리씩 바꾸면서 소수인지를 판별해야 하고
• 바꿔볼 때마다 카운트를 세어줘야 하고
• 바꿨던 번호를 저장해주고 그 번호는 피하도록 표본으로 만들자
• 바꿔야할 자리를 다 바꿔봐도 소수가 안된다면, 아예 다른 숫자로도 변경해봐야 하는데...
• 방법을 찾지 못하고 고민만 하다가 시간 초과

3. 수도코드

const primePassword = (curPwd, newPwd) => {
  if (curPwd === newPwd) { return 0; }
  // 소수인지를 판별해 줄 내부함수 구현
  function isPrime(num) { // 1000부터 판별할거라 조건을 간단하게
    for(let i = 2; i <= Math.floor(Math.sqrt(num)); i++) {
      if(num % i === 0) { return false; }
    } return true;
  }
  let used = [curPwd]; // 썼던 건 다시 쓰면 안되니 표본용으로 저장
  let cnt = 1; // 0번째는 위에서 걸렀으니 1부터 시작 
  let que = [used[used.length - 1]] // 사용했던 마지막 값을 저장
  // while (que.length > 0) {
  // }
};

4. 레퍼런스

const primePassword = (curPwd, newPwd) => {
  // 소수판별용 내부 함수
  function isPrime(num) {
    let sqrt = Math.floor(Math.sqrt(num));
    if (num % 2 === 0) return false;
    for(let i = 3; i <= sqrt; i += 2) {
      if (num % i === 0) return false;
    } return true;
  }
  // 큐에 현재 비밀번호와 변경한 횟수를 함께 넣어준다.
  let Q = [[curPwd, 0]]; 
  // 변경에 사용된 숫자는 저장하여 중복 방지용 표본으로 사용
  let isUsed = [curPwd];
  while (Q.length) {
    let [now, step] = Q.shift();
    if (now === newPwd) return step;
    for (let i = 0; i < 4; i++) { 
      let digits = String(now).split('').map(el => Number(el)) 
      // 이 위치여야 i값에 따라 초기화가 된다
      for (let d = 0; d <= 9; d++) { 
        if (digits[i] !== d) { 
          digits[i] = d; 
          let next = Number(digits.join(''))
          if (next === newPwd) return step + 1; 
          // 원하던 값을 찾으면 뒤에 남은 반복 연산을 두고 리턴하라
          if (next > 1000 && isPrime(next) && !isUsed.includes(next)) {
            Q.push([next, step + 1])
            isUsed.push(next)
          }
        }
      }
    }
  }
}