문제
https://programmers.co.kr/learn/courses/30/lessons/67256
코딩테스트 연습 - 키패드 누르기
[1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL"
programmers.co.kr
풀이
구현 + BFS(최단거리)로 풀 수 있었다.
keyPad라는 2차원 배열을 만들어서 최단거리를 측정할 수 있도록 해주었고, 문자열으로 모든 번호의 좌표를 기록해주어 현재 손가락의 위치가 바뀔 때 마다 해당 문자열을 참조하여 위치를 업데이트 해주었다.
이후에는 문제의 의도대로 1, 4, 7일때 왼손가락, 3, 6, 9일때 오른손가락을 사용할 수 있도록 하고 나머지 2, 5, 8, 0에 대해서는 현재 왼손가락, 오른손가락의 위치와 해당 번호의 좌표를 참조하여 각각의 손가락에 대해 BFS로 최단거리를 측정해주었다. 각각의 최단거리를 얻었다면 다시 문제의 의도대로 더 가까운 손가락이 그 번호를 누를 수 있도록 해주고 해당 손가락의 위치를 업데이트 시켜주면 된다.
이러한 싸이클을 바탕으로 모든 numbers의 원소에 대해 반복하면 정답을 구할 수 있다.
문제를 풀면서 주의할 점은 매번 사용한 손가락의 위치가 바뀌기 때문에 위치를 계속 업데이트 시켜주는 것을 잊지말자.
코드
import java.util.LinkedList;
import java.util.Queue;
class Solution {
final int[] dx = {1,0,-1,0};
final int[] dy = {0,1,0,-1};
int[][] keyPad = {
{1,2,3},
{4,5,6},
{7,8,9},
{-1,0,-1}
};
public String solution(int[] numbers, String hand) {
String answer = "";
String rightLoc = "32";
String leftLoc = "30";
String oneLoc = "00";
String twoLoc = "01";
String threeLoc = "02";
String fourLoc = "10";
String fiveLoc = "11";
String sixLoc = "12";
String sevenLoc = "20";
String eightLoc = "21";
String nineLoc = "22";
String zeroLoc = "31";
for(int i = 0; i < numbers.length; i++) {
if(numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9) {
switch (numbers[i]) {
case 3:
rightLoc = threeLoc;
break;
case 6:
rightLoc = sixLoc;
break;
case 9:
rightLoc = nineLoc;
break;
}
answer+= "R";
} else if(numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7) {
switch (numbers[i]) {
case 1:
leftLoc = oneLoc;
break;
case 4:
leftLoc = fourLoc;
break;
case 7:
leftLoc = sevenLoc;
break;
}
answer+= "L";
} else {
String targetLoc = "";
int rx = Character.getNumericValue(rightLoc.charAt(0));
int ry = Character.getNumericValue(rightLoc.charAt(1));
int lx = Character.getNumericValue(leftLoc.charAt(0));
int ly = Character.getNumericValue(leftLoc.charAt(1));
if(numbers[i] == 2) {
targetLoc = twoLoc;
int tx = Character.getNumericValue(targetLoc.charAt(0));
int ty = Character.getNumericValue(targetLoc.charAt(1));
int leftDist = BFS(tx,ty,lx,ly);
int rightDist = BFS(tx,ty,rx,ry);
if(leftDist < rightDist) {
answer += "L";
leftLoc = targetLoc;
} else if(leftDist > rightDist) {
answer += "R";
rightLoc = targetLoc;
} else {
if(hand.equals("right")) {
answer += "R";
rightLoc = targetLoc;
} else {
answer += "L";
leftLoc = targetLoc;
}
}
} else if(numbers[i] == 5) {
targetLoc = fiveLoc;
int tx = Character.getNumericValue(targetLoc.charAt(0));
int ty = Character.getNumericValue(targetLoc.charAt(1));
int leftDist = BFS(tx,ty,lx,ly);
int rightDist = BFS(tx,ty,rx,ry);
if(leftDist < rightDist) {
answer += "L";
leftLoc = targetLoc;
} else if(leftDist > rightDist) {
answer += "R";
rightLoc = targetLoc;
} else {
if(hand.equals("right")) {
answer += "R";
rightLoc = targetLoc;
} else {
answer += "L";
leftLoc = targetLoc;
}
}
} else if(numbers[i] == 8) {
targetLoc = eightLoc;
int tx = Character.getNumericValue(targetLoc.charAt(0));
int ty = Character.getNumericValue(targetLoc.charAt(1));
int leftDist = BFS(tx,ty,lx,ly);
int rightDist = BFS(tx,ty,rx,ry);
if(leftDist < rightDist) {
answer += "L";
leftLoc = targetLoc;
} else if(leftDist > rightDist) {
answer += "R";
rightLoc = targetLoc;
} else {
if(hand.equals("right")) {
answer += "R";
rightLoc = targetLoc;
} else {
answer += "L";
leftLoc = targetLoc;
}
}
} else if(numbers[i] == 0) {
targetLoc = zeroLoc;
int tx = Character.getNumericValue(targetLoc.charAt(0));
int ty = Character.getNumericValue(targetLoc.charAt(1));
int leftDist = BFS(tx,ty,lx,ly);
int rightDist = BFS(tx,ty,rx,ry);
if(leftDist < rightDist) {
answer += "L";
leftLoc = targetLoc;
} else if(leftDist > rightDist) {
answer += "R";
rightLoc = targetLoc;
} else {
if(hand.equals("right")) {
answer += "R";
rightLoc = targetLoc;
} else {
answer += "L";
leftLoc = targetLoc;
}
}
}
}
}
return answer;
}
int BFS(int targetX, int targetY, int startX, int startY) {
if(targetX == startX && targetY == startY) {
return 0;
}
int[][] dist = new int[4][3];
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 3; j++) {
dist[i][j] = -1;
}
}
Queue<int[]> q = new LinkedList<>();
q.add(new int[] {startX, startY});
dist[startX][startY] = 0;
while (!q.isEmpty()) {
int cur[] = q.poll();
int curX = cur[0];
int curY = cur[1];
for(int dir = 0; dir < 4; dir++) {
int nx = curX + dx[dir];
int ny = curY + dy[dir];
if(nx < 0 || nx >= 4 || ny < 0 || ny >= 3) {
continue;
}
if(dist[nx][ny] != -1 || keyPad[nx][ny] == -1) {
continue;
}
q.add(new int[] {nx, ny});
dist[nx][ny] = dist[curX][curY] + 1;
if(nx == targetX && ny == targetY) {
return dist[targetX][targetY];
}
}
}
return 0;
}
}'프로그래머스' 카테고리의 다른 글
| [프로그래머스] 프로그래머스 Level1 [1차] 다트 게임 Java (카카오 코딩테스트) (0) | 2022.05.25 |
|---|---|
| [프로그래머스] 프로그래머스 Level1 완주하지 못한 선수 Java (0) | 2022.05.25 |
| [프로그래머스] 프로그래머스 Level1 이상한 문자 만들기 Java (0) | 2022.05.23 |
| [프로그래머스] 프로그래머스 Level2 k진수에서 소수 개수 구하기 Java (카카오 코딩테스트) (0) | 2022.05.23 |
| [프로그래머스] 프로그래머스 Level1 예산 C++ (0) | 2022.05.20 |
