[프로그래머스/자바] 숫자 타자 대회 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/136797

프로그래머스

 

dp와 BFS를 이용해 풀었다.

 

처음엔 숫자를 하나씩 DFS로 탐색하고,

현재 손가락 위치에서 왼쪽, 오른쪽을 사용해 해당 depth의 숫자로 갈 수 있는 최소 시간을 BFS로 풀었었다.

numbers의 길이가 100000이라 시간 초과가 났었고, 왼쪽 손가락과 오른쪽 손가락 중 더 가까이에 있는 손가락으로 숫자를 누르는 그리디 방식으로 풀었는데 몇몇 테케를 틀렸었다. 

 

 

 

 

그래서 먼저 1~10에서 1~10으로 갈 수 있는 최소 경로를 BFS로 풀어 w[][] 라는 배열에 저장하고,

이 w 배열을 이용해 가중치를 더해주는 dp 방식으로 풀었다.

 

처음엔 dp로 어떤 값을 메모이제이션 할지 감이 안잡혔는데,

입출력 예 #2인 "5123"을 하나하나 노트에 그려보면 알 수 있다.

 

왼쪽, 오른쪽 손가락이 (4, 6)부터 시작해서, 숫자 5를 왼쪽으로 누르는 경우(5, 6)와 오른쪽으로 누르는 경우(4, 5)

이렇게 쭉 적어나가면 숫자를 누를 수록 겹치는 구간이 많아진다.

 

 

 

즉, dp 배열은 dp[누를 숫자의 인덱스][왼쪽 손가락의 위치][오른쪽 손가락의 위치]로 하고, 

배열 값에는 가중치를 저장한다. (숫자를 누르는 시간)

 

이 dp배열을 충분히 큰 값으로 초기화하고, numbers의 숫자를 앞부터 눌러가면서 더 작은 값으로 갱신하면 된다.

 

점화식을 간단히 표현하자면 아래와 같다.

dp[n][left][right] = min(w[left][n] + dp[n+1][n][right], w[right][n] + dp[n+1][left][n])

 

n번째 숫자를 누르는 최소 시간은,

왼쪽으로 숫자를 누르고 그 다음 숫자를 누르는 경우와

오른쪽으로 숫자를 누르고 그 다음 숫자를 누르는 경우 중 최솟값이다.

 

 

< 단, 숫자 자판은 버튼의 크기가 작기 때문에 같은 숫자 버튼 위에 동시에 두 엄지 손가락을 올려놓을 수 없습니다. >

또한 위 조건을 충족하기 위해서,

왼쪽 손이 이미 눌러야 할 숫자에 있다면 오른쪽으로 그 숫자를 누를 수 없다.

마찬가지로 오른쪽 손이 이미 눌러야 할 숫자에 있다면 왼쪽으로 그 숫자를 누를 수 없다.

만약 숫자를 눌러 손을 이동하면, 한 숫자 버튼 위에 두 손가락을 올려놓게 되기 때문이다.

 

그래서 왼쪽으로 누르는 경우와 오른쪽으로 누르는 경우의 변수를 각각 만들어 충분히 큰 값으로 초기화하고,

위 경우를 충족시킬 때에만 그 변수에 값을 넣는다.

만약, 왼쪽으로 숫자를 누를 수 없는 경우 왼쪽 변수 갱신되지 않고 초기화한 큰 값이 저장되어 있기 때문에

Math.min으로 왼쪽을 누르는 경우와 오른쪽으로 누르는 경우를 비교했을 때, 무조건 오른쪽을 누르는 경우가 반영된다.

 

 

 

 

 

****

numbers의 최대 길이가 100,000이고, 3차원 배열 dp로 구성하면 100,000 * 10 * 10이 되어 메모리 초과가 나지 않을까 생각했는데, 다행히도 모든 테케에 통과했다!

어렵고 재밌었던 문제.... ㅎㅎ

 

 

 

 

전체 코드

import java.util.*;

class Solution {
	int[][] move = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	int[][] diagonal = {{-1, -1}, {1, -1}, {-1, 1}, {1, 1}}; 
	char[][] board = {{'1', '2', '3'}, {'4', '5', '6'}, {'7', '8', '9'}, {'*', '0', '#'}};
	int[][][] dp;
	int[][] w = new int[10][10];
	int[] number;
	int INF = 10000000;
	int n;

	public int solution(String numbers) {
		n = numbers.length();
		number = new int[n];
		dp = new int[n][10][10];

		for(int i=0;i<n;i++) {
			number[i] = numbers.charAt(i) - '0';
			for(int j=0;j<10;j++)
				Arrays.fill(dp[i][j], INF);
		}

		for(int i=0;i<10;i++) 
			for(int j=0;j<10;j++) 
				w[i][j] = 100;

		for(int i=0;i<4;i++)
			for(int j=0;j<3;j++)
				if(board[i][j] != '*' && board[i][j] != '#')
					BFS(i, j, board[i][j] - '0');

		return getMinTime(0, 4, 6);
	}

	int getMinTime(int idx, int left, int right) {
		if(idx == n)
			return 0;

		if(dp[idx][left][right] == INF) {
			int first = INF;
			int second = INF;
			if(right != number[idx]) // 눌러야 할 숫자에 오른쪽 손가락이 위치해있다면 왼쪽 손가락으로 누를 수 없음
				first = w[left][number[idx]] + getMinTime(idx + 1, number[idx], right);
			if(left != number[idx]) // 눌러야 할 숫자에 왼쪽 손가락이 위치해있다면 오른쪽 손가락으로 누를 수 없음
				second = w[right][number[idx]] + getMinTime(idx + 1, left, number[idx]);
			
			dp[idx][left][right] = Math.min(first, second);
		}

		return dp[idx][left][right];
	}

	void BFS(int startR, int startC, int num) {
		Queue<int[]> q = new LinkedList<>();

		q.offer(new int[] {startR, startC, num, 0});
		w[num][num] = 1;

		while(!q.isEmpty()) {
			int[] now = q.poll();

			for(int i=0;i<4;i++) { // 상하좌우 이동
				int nextR = now[0] + move[i][0];
				int nextC = now[1] + move[i][1];
    
				if(check(nextR, nextC) && board[nextR][nextC] != '*' && board[nextR][nextC] != '#'
						&& w[num][board[nextR][nextC] - '0'] > now[3] + 2) {
					w[num][board[nextR][nextC] - '0'] = now[3] + 2;
					w[board[nextR][nextC] - '0'][num] = now[3] + 2;
					q.offer(new int[] {nextR, nextC, board[nextR][nextC] - '0', now[3] + 2});
				}
			}

			for(int i=0;i<4;i++) { // 대각선 이동
				int nextR = now[0] + diagonal[i][0];
				int nextC = now[1] + diagonal[i][1];

				if(check(nextR, nextC) && board[nextR][nextC] != '*' && board[nextR][nextC] != '#'
						&& w[num][board[nextR][nextC] - '0'] > now[3] + 3) {
					w[num][board[nextR][nextC] - '0'] = now[3] + 3;
					w[board[nextR][nextC] - '0'][num] = now[3] + 3;
					q.offer(new int[] {nextR, nextC, board[nextR][nextC] - '0', now[3] + 3});
				}
			}
		}
	}
    
    boolean check(int r, int c) {
		if(r < 0 || r >= 4 || c < 0 || c >= 3)
			return false;
		return true;
	}
    
}