Notice
Recent Posts
Recent Comments
Link
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 |
Tags
- 파이썬
- 백준 2529
- 도커
- 락
- 코딩테스트
- 후위 표기식
- 백트래킹
- 백준 14499
- 백준 15686
- 다익스트라
- 백준 2302
- 9465 스티커
- 스프링
- Spring
- 백준 파이썬
- 프로그래머스
- docker
- 증가하는부분수열
- 스레드
- 백준
- 자바스크립트
- 프로세스
- 백준 10819
- 운영체제
- Spring Security
- 백준 1120
- CS
- 코테
- CI/CD
- 네이버
Archives
- Today
- Total
개발
[프로그래머스] 키패드 누르기 (자바스크립트) 본문
LEVEL1 문제치고 엄청 오래 걸렸던 문제다.
2580의 숫자인 경우 bfs를 통해서 왼손과 오른손과의 거리를 구하는 방식으로 했는데.
다른 사람들의 풀이를 보니 케이스가 적어서 그냥 거리를 직접 계산한거를 사용하거나 좀 더 간단하게 구했다.
코드
function solution(numbers, hand) {
let answer = '';
const leftBtn = [1,4,7];
const rightBtn = [3,6,9];
const graph = [[1,2,3],[4,5,6],[7,8,9],["*",0,"#"]];
let [leftHand, rightHand] = ["*", "#"];
let [lpos, rpos] = [[3,0], [3,2]];
function bfs (a, b, target) {
let queue = [];
let visited = new Array(4);
let dx = [-1,1,0,0];
let dy = [0,0,-1,1];
for (let i = 0; i < 4; i++) {
visited[i] = new Array(3).fill(0);
}
queue.push([a, b, 0]);
visited[a][b] = 1;
while (queue.length > 0) {
let [x, y, count] = queue.shift();
for (let i = 0; i < 4; i++) {
nx = x + dx[i];
ny = y + dy[i];
if (nx < 0 || nx >= 4 || ny < 0 || ny >= 3 || visited[nx][ny] === 1) continue;
if (graph[nx][ny] === target) return count+1;
if (graph[nx][ny] !== target) {
queue.push([nx, ny, count+1]);
visited[nx][ny] = 1;
}
}
}
}
for (let i = 0; i < numbers.length; i++) {
if (leftBtn.includes(numbers[i]) || numbers[i] === leftHand) {
leftHand = numbers[i];
answer += "L";
continue;
}
if (rightBtn.includes(numbers[i]) || numbers[i] === rightHand) {
rightHand = numbers[i];
answer += "R";
continue;
}
for (let i = 0; i < 4; i++) {
for (let j = 0; j < 3; j++) {
if (graph[i][j] === leftHand) {
lpos = [i, j];
}
if (graph[i][j] === rightHand) {
rpos = [i, j];
}
}
}
let diff = bfs(lpos[0], lpos[1], numbers[i]) - bfs(rpos[0], rpos[1], numbers[i]);
if (diff < 0) {
leftHand = numbers[i];
answer += "L";
} else if (diff > 0){
rightHand = numbers[i];
answer += "R";
} else {
if (hand === "left") {
leftHand = numbers[i];
answer += "L";
} else {
rightHand = numbers[i];
answer += "R";
}
}
}
return answer;
}'알고리즘 > 문제' 카테고리의 다른 글
| [백준] 14502 연구소(파이썬) (0) | 2022.07.17 |
|---|---|
| [백준] 1918 후위 표기식(파이썬) (0) | 2022.07.16 |
| [백준] 16928 뱀과 사다리 게임 (0) | 2022.07.06 |
| [프로그래머스] [1차] 비밀지도 (자바스크립트) (0) | 2022.07.01 |
| [프로그래머스] 크레인 인형뽑기 게임 (자바스크립트) (0) | 2022.07.01 |