알고리즘/programmers

[Programmers] 숫자 타자 대회

꾸준함. 2022. 11. 20. 01:58

문제 링크입니다: 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);
}
view raw .cpp hosted with ❤ by GitHub

 

개발환경: 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