
07. Unique Movement Path
Sunhyup Lee. (2024). To be a successful candidate for the coding test. goldenrabbit. p.130.
Problem solving
① The first way to solve the problem : 단계별 사용자 수 계산 후, 직접 실패율 계산
function isValidMove(nx, ny) {
return nx >= -5 && nx <= 5 && ny >=-5 && ny <=5;
// 좌표는 -5, 5 사이의 값을 가질 수 있습니다. 이 범위를 벗어날 경우, 유효하지 않은 이동으로 간주됩니다.
}
function updateLocation(x, y, dir) {
switch ((dir)) {
case "U":
return [x, y + 1];
case "D":
return [x, y - 1];
case "R":
return [x + 1, y];
case "L":
return [x - 1, y];
}
// 이 함수는 현재위치(x, y)와 주어진 방향(dir)에 따라 새로운 좌표를 계산하여 반환합니다.
}
function solution(dirs) {
let x = 0;
let y = 0;
// (x, y)는 시작 위치 (0, 0)입니다.
const visited = new Set();
// 이미 방문한 경롤르 저장할 Set 객체를 생성
// Set: 중복된 경로를 저장하지 않기 위해 사용됩니다. Set은 동일한 값을 여러번 저장하지 않으므로, 방문한 경로를 고유하게 관리할 수 있습니다.
for (const dir of dirs) {
// 주어진 dirs 문자열의 각 문자(방향)를 하나씩 순회합니다.
// dir: 현재 반복 중인 방향을 나타냅니다. 방향은 "U", "D", "R", "L"중 하나일 수 있습니다.
const [nx, ny] = updateLocation(x, y, dir);
// updateLocation 함수를 호출하여, 현재 위치(x, y)에서 dir 방향으로 이동한 후의 새로운 위치(nx, ny)를 계산합니다.
// nx, ny: 새로운 위치의 좌표입니다. updateLocation 함수는 입력된 방향에 따라 새로운 좌표를 반환합니다.
if(isValidMove(nx, ny)) {
// isValidMove(nx, ny) 이 함수는 주어진 좌표(nx, ny)가 -5에서 5 사이의 범위 내에 있는지 확인합니다.
continue;
// 범위를 벗어나면 continue 문을 실행하여, 현재 반복을 건너뛰고 다음 방향으로 넘어갑니다. 이 경우, 위치가 업데이트되지 않고 다음 방향으로 진행합니다.
}
visited.add(`${x}${y}${nx}${ny}`);
visited.add(`${nx}${ny}${x}${y}`);
// visited.add(): 경로를 문자열로 결합하여 Set에 저장합니다. 이때, 두 가지 방향을 모두 저장하영 경로의 양방향을 고려합니다.
// ex) (0. 0)에서 (0, 1)로 이동했다면, visited에는 "0001"과 "0100"이 모두 저장됩니다. 이를 통해 경로의 양방향을 모두 고려합니다.
[x, y] = [nx, ny];
// [x, y] = [nx, ny], 배열구조분해 할당을 사용하여, 새로운 좌표로 현재 위치를 업데이트합니다.
}
return visited.size/2;
// visited.size / 2: visited Set의 크기를 2로 나누는 이유는, 각 경로를 양방향으로 저장했기 때문입니다. 실제 고유 경로의 수는 Set의 크기를 반으로 나눈 값이 됩니다.
}
🧐 시간복잡도는 어떨까?
[Done] exited with code=0 in 0.063 seconds