[JAVA] 프로그래머스 - 키패드 누르기

https://programmers.co.kr/learn/courses/30/lessons/67256

코딩테스트 연습 - 키패드 누르기

 

핸드폰 키패드를 왼손과 오른손으로 누르는 순서를 출력해주는 문제이다.

두손은 *, #에서 시작하고 무조건 1,4,7은 왼손 / 3,6,9는 오른손으로 입력해야하며 가운데 숫자 2,5,8,0은 왼손과 오른손중 가까운 손으로 입력해주면 된다.

 

---

문제 접근 방법

제일 처음에 생각했던 방법은 상하좌우를 탐색해야 한다는 생각과 가운데 숫자의 경우 최소거리에 있는 손이 입력해야 해서 BFS를 이용한 방법을 생각했다.

 

왼손과 오른손의 BFS 함수를 한개씩 만들어서 입력할 번호와 현재 손의 위치에 따른 거리를 계산하여 가까운 거리의 손으로 입력하는 방식으로 문제를 풀었다.

 

풀면서 생각한게 LV1 문제인데 이렇게 LV2같은 LV1문제인가 생각했지만... 풀어본 결과

테케 50%는 맞았지만 나머지 50%에서 전부 시간 초과가 나서 틀린 방식이 됐다.

 

그리고 다른 사람의 풀이를 봤는데.. BFS는 쓸필요도 없고

 

0~9까지에 대한 인덱스를 수학적으로 계산 후 입력할 번호와 손이 위치하고 있는 번호의 인덱스 차이로 거리를 계산하는 방법이였다. 

참고로 조건 중 상하좌우로 움직이는 조건은 결국 위의 인덱스 차이로 계산하면 x(좌우)만큼 움직이는 거리 + y(상하)만큼 움직이는 거리가 되기 때문에 자동으로 조건이 만족된다.

 

그래서 결론적으로 2가지를 계산 할수 있으면된다.

1. 각번호 간의 거리를 계산하는 방법.

2. 1번을 계산하기 숫자가 위치한 인덱스를 구하는 방법.

 

먼저 1 번 계산은

1~0이 2차원배열로 존재한다고 생각할 때 손이 있는 위치의 숫자가 7( 0,2 ) 이고 numbers의 숫자가 5( 1,1 ) 이 나왔다면 거리는 ( 0,2 ) - ( 1,1 ) 즉,  | 0-1 | + | 2-1 | = 2 가 된다.

 

그럼 각 숫자의 인덱스를 계산하기 위해선 어떻게 해야할까

예를 들어 숫자 num의 인덱스(x,y)를 구하고자 할땐.

x = ( num-1 ) / 3;

y = ( num-1 ) % 3;

을 해줘야한다.

 

잘못한 풀이와 정답 풀이를 보자

 

---

풀이

정답 풀이

public class keypadPress2 {

	public static void main(String[] args) {
		int[] numbers = {1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5};
		String hand = "right";
		
		
		solution(numbers,hand);
	}
	
	public static String solution(int[] numbers, String hand) {
        StringBuilder sb = new StringBuilder();
        int leftNum = 10; // 현재 왼손이 있는 숫자 ( * -> 10 은 시작위치)
        int rightNum = 12; // 현재 오른손이 있는 숫자 ( # -> 12 은 시작위치)
        
        for(int i=0; i<numbers.length; i++) {
        	//1,4,7은 무조건 왼손으로 , 3,6,9는 무조건 오른손 입력
        	if(numbers[i]==1 || numbers[i]==4 || numbers[i]==7) {
        		sb.append("L");
        		leftNum = numbers[i];
        	}else if(numbers[i]==3 || numbers[i]==6 || numbers[i]==9) {
        		sb.append("R");
        		rightNum = numbers[i];
        	}else { // 가운데 번호일 경우
        		
        		//왼손부터 numbers[i]까지 거리
        		int Ldis = distance(leftNum, numbers[i]);
        		//오른손부터 numbers[i]까지 거리
        		int Rdis = distance(rightNum, numbers[i]);
        		
        		if(Ldis>Rdis) {
        			sb.append("R");
        			rightNum = numbers[i];
        		}else if(Ldis<Rdis) {
        			sb.append("L");
        			leftNum = numbers[i];
        		}else { //거리가 같을 경우
        			if(hand.equals("right")) {
        				sb.append("R");
        				rightNum = numbers[i];
        			}else {
        				sb.append("L");
        				leftNum = numbers[i];
        			}
        		}
        	}
        }
        
        System.out.println(sb.toString());
        return sb.toString();
	}
	
	public static int distance(int lrNum, int orgNum) {
		if(lrNum==0) lrNum=11; //손이 가리키는 번호가 0이면 11로 치환
		if(orgNum==0) orgNum=11; //입력받은 번호가 0이면 11로 치환
		
		int orgX = orgNum/3; //입력받은 번호의 인덱스 x
		int orgY = 1; //입력받은 번호의 인덱스 y는 가운데 번호라서 무조건 1
		int lrX = (lrNum-1)/3; //현재 손이 가리키는 번호의 인덱스 x
		int lrY = (lrNum-1)%3; //현재 손이 가리키는 번호의 인덱스 y
		
		int dis = Math.abs(orgX-lrX) + Math.abs(orgY-lrY);
		return dis;
	}
}

 

---

 

 

실패한 풀이(BFS 이용)

import java.util.LinkedList;
import java.util.Queue;

public class keypadPress {
	static int[][] keypad = {{1,2,3},{4,5,6},{7,8,9},{11,0,12}};
	static int[] dx = {0,0,-1,1};
	static int[] dy = {-1,1,0,0};
	static boolean[][] check;
	
	public static void main(String[] args) {
		int[] numbers = {1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5};
		String hand = "right";
		
		
		solution(numbers,hand);
	}
	
	public static String solution(int[] numbers, String hand) {
        StringBuilder sb = new StringBuilder();
        int lx = 3;
        int ly = 0;
        int rx = 3;
        int ry = 2;
        int[] Linfo = new int[3];
        int[] Rinfo = new int[3];
        
        
        for(int i=0; i<numbers.length; i++) {
        	check = new boolean[4][3];
        	if(numbers[i]==1 || numbers[i]==4 || numbers[i]==7) {
        		sb.append("L");
        		if(numbers[i]==1) {
        			lx = 0;
        			ly = 0;
        		}else if(numbers[i]==4) {
        			lx = 1;
        			ly = 0;
        		}else {
        			lx = 2;
        			ly = 0;
        		}
        		continue;
        	}else if(numbers[i]==3 || numbers[i]==6 || numbers[i]==9) {
        		sb.append("R");
        		if(numbers[i]==3) {
        			rx = 0;
        			ry = 2;
        		}else if(numbers[i]==6) {
        			rx = 1;
        			ry = 2;
        		}else {
        			rx = 2;
        			ry = 2;
        		}
        		continue;
        	}else {
        		Linfo = leftHand(lx, ly, numbers[i]);
        		Rinfo = rightHand(rx, ry, numbers[i]);
        		if(Linfo[2] > Rinfo[2]) {
        			sb.append("R");
        			rx = Rinfo[0];
        			ry = Rinfo[1];
        		}else if(Rinfo[2] > Linfo[2]) {
        			sb.append("L");
        			lx = Linfo[0];
        			ly = Linfo[1];
        		}else {
        			if(hand.equals("right")) {
        				sb.append("R");
        				rx = Rinfo[0];
            			ry = Rinfo[1];
        			}else {
        				sb.append("L");
        				lx = Linfo[0];
            			ly = Linfo[1];
        			}
        		}
        	}
        }
        	
        return sb.toString();
    }
	
	public static int[] leftHand(int x, int y, int num) {
		int[] info = new int[3];
		Queue<pointKeypad> q = new LinkedList<pointKeypad>();
		q.add(new pointKeypad(x, y, 0));
		check[x][y] = true;
		
		while(!q.isEmpty()) {
			pointKeypad point = q.poll();
			if(keypad[point.pointX][point.pointY]==num) {
				info[0] = point.pointX;
				info[1] = point.pointY;
				info[2] = point.dis;
				return info;
			}
			for(int i=0; i<4; i++) {
				int nx = point.pointX + dx[i];
				int ny = point.pointY + dy[i];
				
				if(nx>=0 && ny>=0 && nx<4 && ny<3) {
					if(!check[nx][ny]) {
						q.add(new pointKeypad(nx, ny, point.dis+1));
					}
				}
			}
		}
		return info;
	}
	
	public static int[] rightHand(int x, int y, int num) {
		int[] info = new int[3];
		Queue<pointKeypad> q = new LinkedList<pointKeypad>();
		q.add(new pointKeypad(x, y, 0));
		check[x][y] = true;
		
		
		while(!q.isEmpty()) {
			pointKeypad point = q.poll();
			if(keypad[point.pointX][point.pointY]==num) {
				info[0] = point.pointX;
				info[1] = point.pointY;
				info[2] = point.dis;
				break;
			}
			
			for(int i=0; i<4; i++) {
				int nx = point.pointX + dx[i];
				int ny = point.pointY + dy[i];
				
				if(nx>=0 && ny>=0 && nx<4 && ny<3) {
					if(!check[nx][ny]) {
						q.add(new pointKeypad(nx, ny, point.dis+1));
					}
				}
			}
		}
		return info;
	}
}


class pointKeypad{
	int pointX;
	int pointY;
	int dis;
	
	public pointKeypad(int x, int y, int dis) {
		this.pointX = x;
		this.pointY = y;
		this.dis = dis;
	}
}

 

---

마치며

솔직히 말해서 인덱스를 구하는 방법을 무슨 공식이 있는것도 아니고 직접 찾아야하기 때문에  바로 떠올리기란 쉽지않다고 생각한다. 그래도 풀기위해선 문제를 많이 풀어봐야 할듯 하다.