4자리 소수 비밀번호를 한번에 한 자리씩 바꿔서 새로운 4자리 비번을 만들 때, 바꾸는 최소 횟수를 구하는 방법을 작성하기
수도코드만 쓰고 해결 못했다.
후보숫자 찾는 건 스도쿠때 했던 거랑 좀 비슷해 보이긴 했다. 거기까지는 생각할 수 있었는데 이해가 완전하지 못했다.
포인트: 최소 동작의 수 라는 말에서 BFS임을 인지하여야 함. 그래프 BFS원리를 이용함.
내가 처음에 제출한 코드(이해한 바는 맞으나 코드 옮기기 실패. BFS 문제 유형으로 풀어야 한다. )
const primePassword = (curPwd, newPwd) => {
// TODO: 여기에 코드를 작성합니다.
/*
문제 이해하기
curPwd는 현재비번, newPwd는 새 비번.
만약에 입력받은 두 비번이 같으면 0을 리턴하면 된다.
서로 다른 경우가 문제.
근데 바꾸는 방법은?
**1. 현재 소수보다 다음으로 큰 소수를 찾되,
2. 다음으로 큰 소수는 현재 소수와 비교 했을 때, 한 자리 수만 달라야 해.
3. 입력받은 두 수 사이에 올 수 있는 모든 소수들을 나열해보자(경계값 포함)
예를 들어서
1009, 1171 - 왜 5가 나오나?
1000의자리: 동일하니 패스
100의 자리: 1로 바꿔본다 1109는 소수니까 변경(1번)
10의 자리: 7로 바꿔본다 1179는 소수아님.
9,8,6,5,4,3,2,1 다넣어본다. 1129는 소수니까 변경(2번)
1의 자리 112x에 1 먼저 넣기 실패. 2,3,...9까지 다 넣기 1123는 소수니까 변경(3번)
다시 10의 자리 돌아가
1173으로 변경하면 실패함. 9,8,...6...1 다 넣어봐. 1193은 소수니까 변경(4번)**
9787, 9923 - 왜 6이 나오나?
전체 반복 횟수: 주어진 현재 비번이 newPwd와 같아질 때까지 반복한다.(스트링으로 변환 후 비교해보면 됨)
*필요 변수: 변경 횟수를 저장할 변수 count = 0;
*/
if(curPwd === newPwd) return 0;
//그 이외의 경우
let count = 0;
return count;
};
레퍼런스 참조 후 작성한 코드
//소수인지 아닌지 판별하는 함수
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;
};
const primePassword = (curPwd,newPwd) => {
//to do...
//일단 두 숫자를 받았을 때 바로 비교해서 같으면 0을 리턴. 바꿀 게 없으니까.
if(curPwd === newPwd) return 0;
//그 이외의 경우는, 바꿔야 한다.
const visited = {curPwd: true} //이전에 쓴 숫자를 또 쓰는 실수 방지용
const queue = [[curPwd,0]]
while(queue.length){
const [num,step] = queue.shift();
//1000의 자리부터 1의 자리까지, 자릿수 단계별로, 바꿔본다.
for(let i = 0; i < 4; i++){
//입력받은 숫자를 자리수별로 바꾸기 위해 배열로 만들어준다. --- **오류원인:for 문 바깥에 있었다.**
const arr = String(num).split('').map(el => Number(el)); //[1,2,3,4] num이 변하면 안돼.
//0-9까지 하나씩 다 넣어보되, 이미 있는 숫자는 건너뛰어야 한다. 다른 숫자일때만 바꿔본다.
for(let n = 0; n <= 9; n++){
//그 숫자가 newPwd와 같은지 확인한다. 같으면 안된다.
if(n !== arr[i]){
arr[i] = n;
const nextPrime = Number(arr.join(''));
if(nextPrime === newPwd) return step + 1;
//그 바꾼 숫자가 소수인지 확인한다.
//1000보다 큰 수인지 확인한다
//이전에 썼던 숫자인지 확인한다.
//위 조건을 다 통과하는 경우에만 인정해준다. (카운트 셀 것)
//실패할 경우, 취소하고 다음 숫자를 붙이는 방식이다.
if(isPrime(nextPrime) && nextPrime > 1000 && !visited[nextPrime]){
visited[nextPrime] = true;
queue.push([nextPrime,step + 1]);
}
}
}
}
}
return -1 //새 비번 만들기 실패 시
}
해설
bfs의 원리를 잘 생각해야 한다.
큐에 원소가 있는 동안 루프를 실행하는데, 루프 안에서, 원소가 이웃한 원소들이 있다면 큐에 이웃들을 먼저 모두 집어넣는다.
위 문제에서 이웃한 원소는 0-9까지의 숫자들을 각 1000, 100, 10, 1의 자리에 넣어본 후 얻어진 소수들이다. 그래서 콘솔에 visited, queue를 찍어보면 엄청나게 많은 데이터가 출력된다.
const [num,step] = queue.shift();
const arr = String(num).split('').map(el => Number(el));
이 부분이 저 위치에 있는 이유:
주어진 숫자를 최소한의 조작으로 바꾸는 게 중요하기 때문에, 일단은 4자리 수 중 다른 수만 먼저 바꿔보는게 더 유리하다. 그래서 모든 자릿수에 대해서 한번씩은 다 바꿔봐야 한다. 운이 좋으면 한번만 바꾸고도 리턴을 할 수 있잖아?
그렇기 때문에 실제적으로 step의 경우에는 자리수가 조건에 맞게 하나씩 바뀔 때만 증가를 하는 게 맞다.