문제
문제 정의
휴대폰 키패드가 있고, 초기에 왼손 엄지손가락은 *, 오른손 엄지손가락은 #에 위치해 있다.
1,4,7번은 왼손을 이용해서 누르고, 3,6,9는 오른손을 이용한다.
가운데 있는 2,5,8,0은 해당 번호에서 가까이 있는 손가락을 이용해서 누르고, 만약 거리가 같을 경우 왼손잡이는 왼손, 오른손잡이는 오른손을 이용해서 누른다.
누른 번호들의 리스트와 왼손잡이인지 오른손잡이인지에 대한 정보가 입력으로 주어졌을 때, 각 번호를 누른 엄지손가락이 왼손인지 오른손인지를 나타내는 문자열을 리턴하는 문제다.
해결방안
풀이 1 (직관적인 방법)
키패드를 2차원 배열로 저장하고, 왼손 엄지손가락과 오른손 엄지손가락의 좌표를 이동시키는 방식으로 풀었다.
function solution(numbers, hand) {
let answer = '';
let left = [3, 0]; // 현재 왼손의 위치 (y,x)
let right = [3, 2]; // 현재 오른손의 위치 (y,x)
const keypad = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9],
['*', 0, '#'],
];
const leftside = [1, 4, 7];
const rightside = [3, 6, 9];
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
const visited = Array.from(Array(4), () => Array(3).fill(false));
for (let i = 0; i < numbers.length; i++) {
const num = numbers[i];
if (leftside.includes(num)) {
answer += 'L';
left = getYX(num);
} else if (rightside.includes(num)) {
answer += 'R';
right = getYX(num);
} else {
const [ly, lx, lcount] = bfs(...left, 0, num); // 왼손 엄지손가락에서 num 까지의 거리
const [ry, rx, rcount] = bfs(...right, 0, num); // 오른손 엄지손가락에서 num 까지의 거리
if (lcount < rcount) {
answer += 'L';
left = [ly, lx];
} else if (lcount > rcount) {
answer += 'R';
right = [ry, rx];
} else {
// 거리가 같을 경우
if (hand === 'left') {
answer += 'L';
left = [ly, lx];
} else {
answer += 'R';
right = [ry, rx];
}
}
}
}
function bfs(y, x, count, target) {
visited.forEach((e) => e.fill(false)); // 방문 기록 초기화
const queue = [[y, x, count]];
visited[y][x] = true;
let front = 0;
while (queue.length > front) {
const [y, x, count] = queue[front++];
if (keypad[y][x] === target) return [y, x, count];
for (let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < 3 && ny < 4 && !visited[ny][nx]) {
visited[ny][nx] = true;
queue.push([ny, nx, count + 1]);
}
}
}
}
// 번호의 y,x 좌표를 반환하는 함수
function getYX(num) {
for (let y = 0; y < 4; y++) {
for (let x = 0; x < 3; x++) {
if (keypad[y][x] === num) {
return [y, x];
}
}
}
}
return answer;
}왼쪽에 포함되는 번호를 눌렀다면 answer+='L'을 하고, 왼손 엄지손가락의 좌표를 해당 번호의 좌표로 이동시키고, 오른쪽에 포함되는 번호를 눌렀다면 answer+='R'을 하고, 오른손 엄지손가락의 좌표로 이동시킨다.
만약 가운데에 있는 번호를 눌렀다면, bfs를 이용해서 "왼손 좌표에서 번호 까지의 거리"와 "오른손 좌표에서 번호 까지의 거리"를 구한 뒤, 두 거리를 비교하도록 해주었다.
위 코드는 직관적이지만 코드의 길이가 너무 길다는 것이 단점이다. 다른 사람의 풀이를 보니 다른 방법으로 푸신 분들도 계서서 해당 방법도 소개해보겠다.
풀이 2
가장 좋아요가 많은 풀이를 참고했다.
직관적으로 와닿진 않지만 코드도 짧고, 시간복잡도가 으로 내가 작성한 코드(풀이1) 보다 성능상으로는 더 좋은 코드라고 할 수 있다.
function solution(numbers, hand) {
hand = hand === 'right' ? 'R' : 'L';
const pos = [0, 3, 3, 3, 2, 2, 2, 1, 1, 1]; // 세로 이동 범위
const h = {
L: [0, 1], // 왼손: [세로 위치, 가로 이동 범위]
R: [0, 1], // 오른손: [세로 위치, 가로 이동 범위]
};
// 왼손 오른손 모두 가로로 이동할 땐 1칸만 이동해주면 되기 때문에 가로는 1로 설정
return numbers
.map((x) => {
// 왼쪽에 있는 번호라면
if (/[147]/.test(x)) {
h.L = [pos[x], 1]; // 세로축 이동
return 'L';
}
// 오른쪽에 있는 번호라면
if (/[369]/.test(x)) {
h.R = [pos[x], 1]; // 세로축 이동
return 'R';
}
// 가운데 있는 번호라면
const distL = Math.abs(pos[x] - h.L[0]) + h.L[1]; // 세로 거리 + 가로 거리
const distR = Math.abs(pos[x] - h.R[0]) + h.R[1]; // 세로 거리 + 가로 거리
// 거리 비교
if (distL < distR) {
h.L = [pos[x], 0];
return 'L';
} else if (distL > distR) {
h.R = [pos[x], 0];
return 'R';
} else {
h[hand] = [pos[x], 0];
return hand;
}
})
.join('');
}pos 배열은 키패드 번호와 인덱스 번호를 일치시킨 배열이다.
배열의 값으로는 높이(?)가 저장되는데, 이 값들은 h.L[0], h.R[0]과 계산하여 세로 거리를 구하는데 사용된다.
h객체는 왼손의 엄지손가락과 오른손의 엄지손가락의 위치를 담은 배열이다. 다만 평범한 x,y좌표와는 차이가 있다.
h.L[0], h.R[0]은 초기값이 0으로 설정되어 있다.
이는 왼손 엄지손가락과, 오른손 엄지손가락이 초기에는 세로축 0번 높이에 있다는 것을 의미한다.
[1, 2, 3] <- 3
[4, 5, 6] <- 2
[7, 8, 9] <- 1
[*, 0, #] <- 0반면에 h.L[1], h.R[1] 은 1로 초기화 되어 있다.
이는 키패드의 가운데에 있는 번호(2,5,8,0)이 나왔을 때 현재 위치에서 가로로 한 칸만 이동하면 된다는 것을 의미한다.
// 가운데 있는 번호라면
const distL = Math.abs(pos[x] - h.L[0]) + h.L[1]; // 세로 거리 + 가로 거리
const distR = Math.abs(pos[x] - h.R[0]) + h.R[1]; // 세로 거리 + 가로 거리
// 거리 비교
if (distL < distR) {
h.L = [pos[x], 0];
return 'L';
} else if (distL > distR) {
h.R = [pos[x], 0];
return 'R';
} else {
h[hand] = [pos[x], 0];
return hand;
}따라서 위 코드처럼 세로 거리와 가로 거리를 더해서 양 손의 엄지손가락의 위치에서 x까지의 거리를 구할 수 있다.
그리고 그 거리를 비교하고, 가운데로 이동한 뒤에는 이동한 손의 h.L[1] or h.R[1]를 0으로 바꾼다.
만약 가운데 번호를 누른 뒤, 다시 가운데 번호를 누르는 경우에는 세로축으로만 이동해주면 되기 때문이다.
만약 가운데로 이동한 뒤, 왼쪽 혹은 오른쪽 번호를 눌러야 하는 경우에는 최단 거리를 계산할 필요 없이 왼쪽에 있는 번호라면 왼쪽 엄지손가락을 이용하면 되고, 오른쪽에 있는 번호라면 오른쪽 엄지손가락을 이용하면 된다.
// 왼쪽에 있는 번호라면
if (/[147]/.test(x)) {
h.L = [pos[x], 1]; // 세로축 이동
return 'L';
}
// 오른쪽에 있는 번호라면
if (/[369]/.test(x)) {
h.R = [pos[x], 1]; // 세로축 이동
return 'R';
}이때 다시 h.L[1] or h.R[1] 을 1로 바꿔줌으로써 가운데로 이동했을 때 가로축 거리를 계산해줄 수 있도록 한다.
속도 차이
풀이 1
풀이 2
