프로그래머스 숫자 타자 대회 문제 풀이를 진행하였습니다.
문제 해석
문제를 읽으면 아래와 같은 해석이 가능합니다.
위와 같은 모양의 숫자 자판이 있습니다.
두 엄지 손가락을 이용해 타이핑을 하며, 시작은 왼손 엄지 4, 오른손 엄지 6 위에 두고 진행합니다.
엄지로 주어진 수를 누르는데 일정량의 가중치가 주어지는데
이동하지 않고 제자리에서 다시 누르는 것은 가중치가 1
상하좌우로 인접한 숫자로 이동하여 누르는 것은 가중치가 2
대각선으로 인접한 숫자로 이동하여 누르는 것은 가중치가 3
위와 같은 가중치를 따르며 같지 않고 인접하지 않은 숫자를 누를 때는 위 규칙에 따라 가중치 합이 최소가 되는 경로를 따릅니다.
주어진 문자열을 타이핑했을 때 가중치의 최소값을 구해야합니다.
문제 풀이
일단 각 숫자에서 나머지 숫자를 눌렀을 때 주어지는 가중치를 알아두면 좋을 것 같아 풀기 전 가중치를 알 수 있는 2차원 배열을 만들어 값을 채워주었습니다.
다음 숫자를 누를 때 왼손과 오른손 위치로부터 가중치가 적은 쪽으로 눌러주는 방법은, 반례가 존재하기 때문에 이런 방법은 사용하지 못합니다.
또한 모든 경우를 찾아보기에는 입력받는 숫자의 수가 100000개이므로 시간초과가 나올 것입니다.
그러므로 전에 계산했던 가중치들을 저장하는 dp를 사용하며 문제를 풀어보았습니다.
예시를 손수 그려가며 답을 맞춰보면 여러 개의 결과들 중 왼손 오른손 순서는 다르지만 왼손 오른손의 위치가 같은 지점이 생깁니다.
이러한 중복되는 부분들을 최솟값으로 바꿔 계산해주게 되면 계산하는 양을 확실히 줄여 시간초과를 해결할 수 있습니다.
이러한 중복되는 부분들을 쉽게 찾기 위하여 DFS대신 BFS를 사용하여 계산을 진행해줍니다.
마지막까지 계산 후 만들어진 DP배열 내의 숫자들 중 최솟값을 찾아 return해주면 됩니다.
전체 코드
dp를 사용하는 것은 알았지만 어떤 식으로 사용해야하는지 찾기 위해 여러 시행착오를 겪었습니다.
#include <bits/stdc++.h>
#include <string>
#include <vector>
using namespace std;
int INF = INT_MAX;
string number;
queue<vector<int>> q;
vector<vector<vector<int>>> dp;
vector<vector<int>> moveCost;
int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};
int numpad[4][3] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9},
{-1, 0, -1}};
vector<int> calcMoveCost(int x, int y)
{
vector<vector<int>> movingCost(4, vector<int>(3, 1000));
movingCost[x][y] = 0;
for(int l = 0; l < 2; l++)
{
for(int i = 0; i < 3; i++)
{
for(int j = 0; j < 3; j++)
{
for(int k = 0; k < 8; k++)
{
if(i + dx[k] < 0 || i + dx[k] > 3 || j + dy[k] < 0 || j + dy[k] > 2)
continue;
if(numpad[i+dx[k]][j+dy[k]] >= 0 && numpad[i+dx[k]][j+dy[k]] <= 9)
{
if(k < 4)
{
movingCost[i+dx[k]][j+dy[k]] = min(movingCost[i+dx[k]][j+dy[k]], movingCost[i][j] + 2);
}else{
movingCost[i+dx[k]][j+dy[k]] = min(movingCost[i+dx[k]][j+dy[k]], movingCost[i][j] + 3);
}
}
}
}
}
}
vector<int> v;
v.push_back(movingCost[3][1]);
for(int i = 0; i < 3; i++)
{
for(int j = 0; j < 3; j++)
{
v.push_back(movingCost[i][j]);
}
}
return v;
}
void bfs(int index, int left, int right, int cost)
{
queue<vector<int>> q;
q.push({left, right});
for(int i = 0; i < number.size(); i++)
{
int qSize = q.size();
for(int j = 0; j < qSize; j++)
{
vector<int> cur = q.front(); q.pop();
int curNum = number[i]-48; //다음으로 눌러야 되는 수
int prevCost = 0; //전에 계산했던 오른손과 왼손 위치의 값
if(i != 0)
prevCost = dp[i-1][cur[0]][cur[1]];
int leftCost = moveCost[cur[0]][curNum]; //왼손을 눌러야 되는 수로 움직였을 때의 가중치
int rightCost = moveCost[cur[1]][curNum]; //오른손을 눌러야 되는 수로 움직였을 때의 가중치
if(cur[1] != curNum)
{
if(prevCost + leftCost < dp[i][curNum][cur[1]]) //전에 계산했던 값보다 작을 경우
{
if(dp[i][curNum][cur[1]] == INF) //중첩되는 왼손 오른손이 있을 경우에는 값만 변경
q.push({curNum, cur[1]});
dp[i][curNum][cur[1]] = prevCost + leftCost;
}
}
if(cur[0] != curNum)
{
if(prevCost + rightCost < dp[i][cur[0]][curNum]) //전에 계산했던 값보다 작을 경우
{
if(dp[i][cur[0]][curNum] == INF) //중첩되는 왼손 오른손이 있을 경우에는 값만 변경
q.push({cur[0], curNum});
dp[i][cur[0]][curNum] = prevCost + rightCost;
}
}
}
}
}
int solution(string numbers) {
int answer = INF;
int index = 1;
number = numbers;
//자판에서 자판까지 이동할 경우 생기는 가중치 계산
moveCost.push_back({1, 7, 6, 7, 5, 4, 5, 3, 2, 3});
for(int i = 0; i < 3; i++)
{
for(int j = 0; j < 3; j++)
{
moveCost.push_back(calcMoveCost(i, j));
moveCost[index][index] = 1;
index++;
}
}
int left = 4;
int right = 6;
dp.assign(numbers.size(), vector<vector<int>>(10, vector<int>(10, INF)));
bfs(0, left, right, 0);
//최솟값을 찾아 return
for(int i = 0; i < 10; i++)
{
for(int j = 0; j < 10; j++)
{
answer = min(answer, dp[number.size()-1][i][j]);
}
}
return answer;
}출저
https://school.programmers.co.kr/learn/courses/30/lessons/136797
