문제
현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아 지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음 과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다.
현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성 하세요.
▣ 입력설명
첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000 까지이다.
▣ 출력설명
점프의 최소횟수를 구한다. 답은 1이상입니다.
예시
| S | E | Result |
|---|---|---|
| 5 | 14 | 3 |
| 8 | 3 | 5 |
풀이
- 현수가 한 번 이동 할 때 움직일 수 있는 거리의 경우의 수들을 배열로 만든다.
[1 , -1 , 5] - BFS 알고리즘으로 위에서 만든 배열의 각 원소만큼 현수의 위치를 이동시키면, 아래와 같이 트리가 뻗어나간다.
.........................(5)
.....(6) ..............(4) ................(10)
..(7 5 11) ........(5 3 9) .........(11 9 15) - 각 깊이마다 3의 n승 만큼 이동해봤을 때 모든 경우의 수를 검사해본 것이므로, 이를 위해
thress라는 배열에 1~10001 까지 3의 n승 들을 저장해놓는다. (이 방법은 시간복잡도가 너무 높고, 정답도 아니었다....) - BFS 안에서 경우의 수 카운팅을 하던
count가thress의 원소면 현수가 한 번 이동한 모든 경우의 수를 검사해 본 것이므로answer를 1 늘린다. - 위 과정에서 현재 위치가 소의 위치가 같아지면
answer를 반환한다. - 위 풀이는 문제에서 주어진 테스트케이스는 통과했지만, (1, 2) 같은 단순한 테스트케이스를 통과하지 못했고, 무엇보다 시간복잡도가 너무 높은 풀이라서 아쉽다.
코드
const solution = (person, cow) => {
let answer = 1;
const jump = [1, -1, 5];
const queue = [];
let count = 0;
const threes = [3];
if (person === cow) return 1;
while (threes[threes.length - 1] < 10001) {
threes.push(threes[threes.length - 1] * 3);
}
queue.push(person);
while (queue.length) {
const curPos = queue.shift();
if (curPos === cow) break;
count++;
if (threes.indexOf(count) !== -1) answer++;
for (let j of jump) {
queue.push(curPos + j);
if (curPos + j === cow) return answer;
}
}
};