- 문제
다음의 조건을 만족하면서 현재의 비밀번호('curPwd')를 새 비밀번호(newPwd)로 변경하는 데 필요한 최소 동작의 수를 리턴해야 합니다.
- 한 번에 한 개의 숫자만 변경가능하다.
- 4자리의 소수(prime)인 비밀번호로만 변경가능하다.
정리하면, 비밀번호가 계속 소수를 유지하도록 숫자 한 개씩을 바꿔갈 때 현재 비밀번호에서 새 비밀번호로 바꾸는 데 최소 몇 개의 숫자를 변경해야 하는지를 리턴해야 합니다.
소수: 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 (1, 3, 5, 7, 11...)
입출력 예시:
let output = primePassword(1033, 1033);
console.log(output); // --> 0
output = primePassword(3733, 8779);
console.log(output); // --> 3 (3733 -> 3739 -> 3779 -> 8779)- 풀이
현재 비밀번호의 일의 자리 수와 새 비밀번호의 일의 자리 수로 변환하여 소수인지 확인, 소수이면 카운트 추가
소수가 아니면 break하고 십의 자리를 비교하여 확인
const primePassword = (curPwd, newPwd) => {
// TODO: 여기에 코드를 작성합니다.
let count = 0;
const oneNum =
const isPrime = function (num) {
if(num % 2 === 0) {
return false;
}
let sqrt = Math.floor(Math.sqrt(num));
for (let i = 3; i <= sqrt; i+=2) {
if (num % i === 0) {
return false
}
}
return true
}
};여기까지 풀고 풀지 못했다ㅜㅜ
소수를 찾는 식을 구하고 각 자리수를 바꾸면서 소수인 경우 카운트를 늘려가려고 했지만, 구현이 너무 어려웠다.
레퍼런스 코드
// 1. 내가 처음 생각한 대로 소수 확인 함수가 하나 필요하다.
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;
};
// 2. 각 자리수를 바꿔가면서 소수 판별할 수 있도록 각 숫자의 배열로 만드는 함수와 다시 수로 조합하는 함수가 필요하다.
// 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));
};
const joinNum = (digits) => Number(digits.join(''));
// 3. 본격적으로 식 시작한다.
const primePassword = (curPwd, newPwd) => {
// 3-1. 기본식
if (curPwd === newPwd) return 0;
// 3-2. bfs (너비우선탐색)을 진행하기위해 친구인 queue가 필요하다.
// 확인한 수를 다시 확인을 하지 않기 위한 isChecked 변수가 하나 필요하다.
// 여기에서는 queue에서 실제로 넣고 빼고를 실행하기 않고 front, rear를 활용하여 queue의 길이를 임의로 활용한다.
let front = 0;
let rear = 0;
const queue = [];
// front와 rear 값이 같으면, queue 배열이 0이라고 임의로 활용하는 isEmpty 함수가 필요하다.
// front와 rear 그리고 queue가 동시에 움직여야 한다는 것을 알 수 있다.
const isEmpty = (queue) => front === rear;
// 3-2-1. queue의 요소를 enqueue, dequeue해주는 함수가 필요하다.
// 먼저 enqueue 함수에는 [필요한 동작수, 숫자]로 이뤄진 item 인자를 queue에 넣어준다.
const enQueue = (queue, item) => {
queue.push(item);
rear++
// rear값을 증가시켜 queue에 요소 하나가 들어간 것으로 임의로 표기한다.
}
// dequeue 함수에 현재 queue에 front(현재??)를 리턴하고 front값을 증가 시킨다.
// 나중에 dequeue할 item이 enqueue에 들어간 item이어야 하므로 front값이 증가되어야 한다.
const deQueue = (queue) => {
const item = queue[front];
front++;
return item
}
// 3-3. isVisited 배열을 하나 만들고 현재 조회하는 수가 이미 조회했던 수인지 판명한다. 그래야 최소 동작의 횟수를 구할 수 있다.
// 4자리 수이니 10000개의 false로 구성된 배열을 만들고 현재 수 자리에 true를 넣는다.
const isVisited = Array(10000).fill(false);
isVisited[curPwd] = true;
// 3-4. bfs의 시작점
// queue에 [필요한 동작수, 비밀번호]
enQueue(queue, [0, curPwd]);
// 3-5. bfs가 시작된다. 친구인 while문이 필요하다.
while (isEmpty(queue) === false) {
const [step, num] = deQueue(queue) // 큐에 넣어 준 item을 각각 step과 num이 되도록 구조분해할당을 해둔다.
// 3-5-1. 각 자리수마다 변경을 시도할 예정이니 4번 반복한다.
for (let i = 0; i < 4; i++) {
// 수를 4개로 분해해 주고
const digits = splitNum(num);
// 각 자리의 수를 본인 수 제외하고 모두 바꿔본다 0-9까지.
for (let d = 0; d < 10; d++) {
if ( d !== digits[i]) {
// 다른 수로 바꿔보고
digits[i] = d;
// 다시 수로 변경을 해주고
const next = joinNum(digits)
// 만약 새로운 수가 newPwd와 같다면 현재 step에서 1를 증가시키고 반환한다
// (새로운 수가 나오기까지 한번 변경한 것이니까)
if (next === newPwd) return step + 1;
// 1,000보다 큰 소수여야 하고, 방문된 적이 없어야 한다.
if (next > 1000 && isPrime(next) && isVisited[next] === false) {
// 조회했다고 표기하고
isVisited[next] = true;
// 변경횟수, 새로운 수를 queue에 넣어 준다.
enQueue(queue, [step + 1, next]);
}
}
}
}
}
return -1;
}여전히 복잡하고 어렵다. 이진탐색, dfs, bfs를 제대로 공부해 놓지 않으면 큰일 나겠다. 단단히 공부해 두어야겠다.
Log