[프로그래머스][C++] 숫자 타자 대회
숫자 타자 대회
문제 링크
분석
키패드는 $4 \times 3$ 배열입니다.
1 2 3
4 5 6
7 8 9
* 0 #
처음 왼손 엄지는 4, 오른손 엄지는 6에 위치해 있습니다.
손가락을 통해 numbers
의 순서대로 각 숫자를 눌러야 합니다.
이때, 손가락의 이동에는 가중치가 있으며, 두 손가락이 동시에 같은 버튼에 있을 수 없습니다.
이렇게 numbers
의 각 숫자를 누르면서 생기는 총 가중치의 최솟값을 찾아 반환해야합니다.
가중치는 다음과 같습니다.
- 같은 자리일 경우
1
- 인접한 상하좌우 이동일 경우
2
- 인접한 대각선 이동일 경우
3
- 인접하지 않은 숫자는 위의 인접한 이동을 통한 이동으로 가중치가 결정
풀이
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;
// 숫자의 키패드 위치를 행과 열로 반환하는 함수
pair<int, int> getPos(int num)
{
// 0은 키패드에서 3, 1에 위치합니다.
if (num == 0)
{
return {3, 1};
}
// 3 x 3으로 배치되므로, 행(row), 열(col)은 다음 식으로 구할 수 있습니다.
return {(num - 1) / 3, (num - 1) % 3};
}
int getCost(int from, int to)
{
// 이미 같은 위치인 경우
if (from == to)
{
return 1;
}
// form과 to의 좌표를 구해 저장합니다.
auto [r1, c1] = getPos(from);
auto [r2, c2] = getPos(to);
// 행과 열의 차이에 대한 절대값을 저장합니다.
int rowDiff = abs(r1 - r2);
int colDiff = abs(c1 - c2);
// 대각선 이동 횟수로 행과 열 차이 중 작은 값이 됩니다.
int diagonalMoves = min(rowDiff, colDiff);
// 직선 이동 횟수로 차이가 큰 값 중 대각선 이동 횟수를 뺀 값입니다.
int straightMoves = max(rowDiff, colDiff) - diagonalMoves;
// 각 이동 횟수에 가중치를 곱해줍니다.
return 3 * diagonalMoves + 2 * straightMoves;
}
int dfs(const string& numbers, int index, int left, int right, vector<vector<vector<int>>>& dp)
{
// 재귀 종료 조건으로서 모든 숫자를 다 누른 경우 비용이 0입니다.
if (index == numbers.size())
{
return 0;
}
// 이미 계산한 상태인 경우 저장된 값 반환
int& cachedDPValue = dp[index][left][right];
if (cachedDPValue != INT_MAX)
{
return cachedDPValue;
}
// 현재 눌러야 할 숫자
int num = numbers[index] - '0';
// 왼손이 num 위치로 이동할 때 오른손과 겹치지 않는 경우
if (num != right)
{
// 왼손에서 num 위치로 이동할 경우의 이동 비용
int leftCost = getCost(left, num);
// 다음 숫자를 누르기 위해 재귀 호출
int resLeft = dfs(numbers, index + 1, num, right, dp);
// 왼손이 현재 숫자를 눌렀을 때 재귀 결과가 유효한 경우
if (resLeft != INT_MAX)
{
// 비용 최소값 갱신
cachedDPValue = min(cachedDPValue, leftCost + resLeft);
}
}
// 오른손이 num 위치로 이동할 때 왼손과 겹치지 않는 경우
if (num != left)
{
// 오른손에서 num 위치로 이동할 경우의 이동 비용
int rightCost = getCost(right, num);
// 다음 숫자를 누르기 위해 재귀 호출
int resRight = dfs(numbers, index + 1, left, num, dp);
// 오른손이 현재 숫자를 눌렀을 때 재귀 결과가 유효한 경우
if (resRight != INT_MAX)
{
// 비용 최소값 갱신
cachedDPValue = min(cachedDPValue, rightCost + resRight);
}
}
// 현재 상태에서 누적된 최소 비용 반환
return cachedDPValue;
}
int solution(string numbers) {
// dp 배열을 초기화 합니다.
// dp[index][left][right]는 index번째 숫자를 누를 때 왼손가락(left)과 오른손가락(right)의 위치에 따른 최소 비용을 저장
vector<vector<vector<int>>> dp(numbers.size() + 1, vector<vector<int>>(11, vector<int>(11, INT_MAX)));
return dfs(numbers, 0, 4, 6, dp);
}
성능 요약
시간 복잡도는 $O(n \times 100)$입니다.
DFS
함수의 호출 $O(n \times 10 \times 10)$
공간 복잡도는 $O(n \times 121)$입니다.
- 각 손가락 위치마다의 최소 비용을 저장한
dp
$O(n + 1 \times 11 \times 11)$ DFS
함수의 호출 스택 $O(n)$- $O(n + 1 \times 11 \times 11) + O(n)$
테스트 성능
테스트 1 〉 통과 (0.01ms, 3.68MB)
테스트 2 〉 통과 (0.01ms, 3.68MB)
테스트 3 〉 통과 (0.01ms, 4.19MB)
테스트 4 〉 통과 (0.01ms, 4.2MB)
테스트 5 〉 통과 (0.01ms, 4.2MB)
테스트 6 〉 통과 (0.01ms, 3.62MB)
테스트 7 〉 통과 (0.02ms, 4.2MB)
테스트 8 〉 통과 (0.01ms, 4.21MB)
테스트 9 〉 통과 (0.02ms, 4.2MB)
테스트 10 〉 통과 (0.01ms, 3.63MB)
테스트 11 〉 통과 (0.03ms, 3.63MB)
테스트 12 〉 통과 (0.03ms, 4.16MB)
테스트 13 〉 통과 (0.03ms, 3.59MB)
테스트 14 〉 통과 (0.03ms, 4.21MB)
테스트 15 〉 통과 (0.03ms, 4.41MB)
테스트 16 〉 통과 (29.00ms, 25.8MB)
테스트 17 〉 통과 (48.69ms, 39.3MB)
테스트 18 〉 통과 (80.36ms, 56.8MB)
테스트 19 〉 통과 (129.68ms, 79.5MB)
테스트 20 〉 통과 (186.24ms, 108MB)
댓글남기기