문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/136797
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
numbers의 길이가 최대 십만이기 때문에 브루트 포스로 풀 수 없는 문제였습니다.
따라서, 저는 오랜만에 DP로 접근해서 풀었습니다.
알고리즘은 아래와 같습니다.
1. 숫자는 0 ~ 9로 한정되어있기 때문에 이차원 배열을 통해 최소 가중치를 미리 구해줍니다.
2. [numbers의 최대 길이][왼손이 누를 수 있는 0~9까지의 숫자][오른손이 누를 수 있는 0~9까지의 숫자] 와 같이 3차원 DP 배열을 선언하고 아래와 같은 로직으로 전개합니다.
2.1 왼손가락 혹은 오른손가락이 현재 눌러야할 숫자에 올라가 있으면 가중치 1을 더한 상태로 다음 숫자로 넘어갑니다.
2.2 왼손가락이 움직이거나 오른손가락을 움직입니다. 이때, 둘 중 더 적은 가중치의 합을 반환해야 하므로 두 케이스 중 최소인 가중치를 반환합니다.
주의: 재귀함수의 매개변수로 numbers를 넘길 경우 시간 초과가 발생하므로 전역 변수로 numbers를 복사한 상태로 사용하는 것을 권고합니다.
#include <string> | |
#include <vector> | |
#include <cstring> | |
#include <algorithm> | |
using namespace std; | |
const int MAX = 1e5 + 1; | |
const int NUMBER_MAX = 10; | |
// 자판 이동 비용을 미리 구해놓음 | |
const int steps[NUMBER_MAX][NUMBER_MAX] = { | |
{ 1, 7, 6, 7, 5, 4, 5, 3, 2, 3 }, | |
{ 7, 1, 2, 4, 2, 3, 5, 4, 5, 6 }, | |
{ 6, 2, 1, 2, 3, 2, 3, 5, 4, 5 }, | |
{ 7, 4, 2, 1, 5, 3, 2, 6, 5, 4 }, | |
{ 5, 2, 3, 5, 1, 2, 4, 2, 3, 5 }, | |
{ 4, 3, 2, 3, 2, 1, 2, 3, 2, 3 }, | |
{ 5, 5, 3, 2, 4, 2, 1, 5, 3, 2 }, | |
{ 3, 4, 5, 6, 2, 3, 5, 1, 2, 4 }, | |
{ 2, 5, 4, 5, 3, 2, 3, 2, 1, 2 }, | |
{ 3, 6, 5, 4, 5, 3, 2, 4, 2, 1 } | |
}; | |
// DP | |
// numbers.length, 왼손가락, 오른손가락이 위치한 숫자 | |
int cache[MAX][NUMBER_MAX][NUMBER_MAX]; | |
string copyNumbers; | |
int func(int idx, int left, int right) | |
{ | |
if (idx == copyNumbers.length()) | |
{ | |
return 0; | |
} | |
int& result = cache[idx][left][right]; | |
if (result != -1) | |
{ | |
return result; | |
} | |
int cur = copyNumbers[idx] - '0'; | |
// 현재 손가락이 자판에 위치하면 비용은 1 | |
if (left == cur || right == cur) | |
{ | |
return result = 1 + func(idx + 1, left, right); | |
} | |
// 왼손가락 혹은 오른손가락이 움직였을 때 | |
return result = min(func(idx + 1, cur, right) + steps[left][cur] | |
, func(idx + 1, left, cur) + steps[right][cur]); | |
} | |
int solution(string numbers) { | |
memset(cache, -1, sizeof(cache)); | |
copyNumbers = numbers; | |
return func(0, 4, 6); | |
} |

개발환경: Programmers IDE
지적, 조언, 질문 환영합니다! 질문 남겨주세요~
'알고리즘 > programmers' 카테고리의 다른 글
[Programmers] 디펜스 게임 (2) | 2022.12.10 |
---|---|
[Programmers] 할인 행사 (0) | 2022.12.03 |
[Programmers] 숫자 짝궁 (0) | 2022.10.10 |
[Programmers] 파괴되지 않은 건물 (1) | 2022.09.27 |
[Programmers] 코딩 테스트 공부 (0) | 2022.08.26 |