프로그래머스 2023.07.24 (1Lv 키패드 누르기)
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제
문제 설명
스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다.
이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다.
1 2 3 4 5 6 7 8 9 * 0 #
맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.
1. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
2. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
3. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
4. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.
4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.
순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해주세요.
제한사항
◈ numbers 배열의 크기는 1 이상 1,000 이하입니다.
◈ numbers 배열 원소의 값은 0 이상 9 이하인 정수입니다.
◈ hand는 "left" 또는 "right" 입니다.
◈ "left"는 왼손잡이, "right"는 오른손잡이를 의미합니다.
◈ 왼손 엄지손가락을 사용한 경우는 L, 오른손 엄지손가락을 사용한 경우는 R을 순서대로 이어붙여 문자열 형태로 return 해주세요.
입출력 예
numbers hand result [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL"
입출력 예에 대한 설명
입출력 예 #1
오른손잡이가 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5]를 순서대로 누르면 사용한 손은 "LRLLLRLLRRL"이 됩니다.
<더 자새한 예제는 프로그래머스 사이트 해당 문제 참고>
입출력 예 #2
왼손잡이가 [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2]를 순서대로 누르면 사용한 손은 "LRLLRRLLLRR"이 됩니다.
입출력 예 #3
오른손잡이가 [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]를 순서대로 누르면 사용한 손은 "LLRLLRLLRL"이 됩니다.
코딩
#include <string>
#include <vector>
#include <queue>
#define None -1
using namespace std;
struct tNode
{
int LeftNum;
int RightNum;
int UpNum;
int DownNum;
int Dist;
bool bvisit;
tNode(int Lf, int Rt, int Up, int Dn)
{
LeftNum = Lf;
RightNum = Rt;
UpNum = Up;
DownNum = Dn;
Dist = 0;
bvisit = false;
}
};
void Clear(vector<tNode>& _vecPad)
{
for (size_t i = 0; i < _vecPad.size(); ++i)
{
_vecPad[i].bvisit = false;
_vecPad[i].Dist = 0;
}
}
int calcul(vector<tNode>& _vecPad, int _StartNum, int _TargetNum)
{
queue<int> q;
q.push(_StartNum);
_vecPad[_StartNum].bvisit = true;
while (!q.empty())
{
int x = q.front();
q.pop();
if (x == _TargetNum)
{
return _vecPad[x].Dist;
}
int iLeft = _vecPad[x].LeftNum;
int iRight = _vecPad[x].RightNum;
int iUp = _vecPad[x].UpNum;
int iDown = _vecPad[x].DownNum;
if (_TargetNum == iLeft
|| _TargetNum == iRight
|| _TargetNum == iUp
|| _TargetNum == iDown)
{
return _vecPad[x].Dist + 1;
}
if (iLeft != None && !(_vecPad[iLeft].bvisit))
{
q.push(iLeft);
_vecPad[iLeft].Dist = _vecPad[x].Dist + 1;
}
if (iRight != None && !(_vecPad[iRight].bvisit))
{
q.push(iRight);
_vecPad[iRight].Dist = _vecPad[x].Dist + 1;
}
if (iUp != None && !(_vecPad[iUp].bvisit))
{
q.push(iUp);
_vecPad[iUp].Dist = _vecPad[x].Dist + 1;
}
if (iDown != None && !(_vecPad[iDown].bvisit))
{
q.push(iDown);
_vecPad[iDown].Dist = _vecPad[x].Dist + 1;
}
}
}
string solution(vector<int> numbers, string hand) {
string answer = "";
vector<tNode> vec_Pad;
// 패드 만들기
vec_Pad.push_back(tNode(10, 11, 8, None)); // 0번 숫자
vec_Pad.push_back(tNode(None, 2, None, 4)); // 1
vec_Pad.push_back(tNode(1, 3, None, 5)); // 2
vec_Pad.push_back(tNode(2, None, None, 6)); // 3
vec_Pad.push_back(tNode(None, 5, 1, 7)); // 4
vec_Pad.push_back(tNode(4, 6, 2, 8)); // 5
vec_Pad.push_back(tNode(5, None, 3, 9)); // 6
vec_Pad.push_back(tNode(None, 8, 4, 10)); // 7
vec_Pad.push_back(tNode(7, 9, 5, 0)); // 8
vec_Pad.push_back(tNode(8, None, 6, 11)); // 9
vec_Pad.push_back(tNode(None, 0, 7, None)); // 10 *
vec_Pad.push_back(tNode(0, None, 9, None)); // 11 #
int curLeftPos = 10;
int curRightPos = 11;
for (size_t i = 0; i < numbers.size(); ++i)
{
int iTargetNum = numbers[i];
if (iTargetNum == 1
|| iTargetNum == 4
|| iTargetNum == 7)
{
answer += "L";
curLeftPos = iTargetNum;
}
else if (iTargetNum == 3
|| iTargetNum == 6
|| iTargetNum == 9)
{
answer += "R";
curRightPos = iTargetNum;
}
else
{
Clear(vec_Pad);
int LeftHandDist = calcul(vec_Pad, curLeftPos, iTargetNum);
Clear(vec_Pad);
int RightHandDist = calcul(vec_Pad, curRightPos, iTargetNum);
if (LeftHandDist < RightHandDist)
{
answer += "L";
curLeftPos = iTargetNum;
}
else if (LeftHandDist == RightHandDist)
{
if (hand == "left")
{
answer += "L";
curLeftPos = iTargetNum;
}
else if (hand == "right")
{
answer += "R";
curRightPos = iTargetNum;
}
}
else
{
answer += "R";
curRightPos = iTargetNum;
}
}
}
return answer;
}너무 코드가 길어서 마음에는 들지 않지만.. 코드 설명을 해보자면,
numbers에 담긴 수를 확인해, 해당 수가 1, 4, 7이면, 왼쪽손을 사용하고, 3, 6, 9이면, 오른손을 사용하도록 코드를 짰다.
(추가적으로 이 과정에서 현재 오른손과 왼손위치를 해당 수로 변경해주도록 짰다. -> 이후 BFS로 최단경로 탐색을 할때 필요하기 때문)
제일 문제는 가운데에 위치한 2, 5, 8, 0 숫자인데, 이 경우 현재 왼손과 오른손 위치로 부터 더 가까운 손으로 패드를 누르도록 짜야한다.
나는 경로를 찾는 알고리즘 중 BFS를 이용해서 구해보려했다.
때문에 숫자 패드를 그래프 형태로 구현했다. tNode 구조체를 선언해 본인의 왼쪽, 오른쪽, 상, 하에 위치한 숫자패드를 넣을 수 있도록 만들고, BFS도중 방문처리를 해줄 bool 변수와 최단 경로를 알기위한 거리값을 넣어줄 int 변수를 담도록 만들어 주었다.
이후, vector<tNode>를 선언해 본인의 숫자와 일치하는 vector의 index에 넣어 숫자 패드를 완성해주었다.
이때, 본인의 좌우상하에 위치한 수가 없을 경우 -1을 넣어주도록 만들었는데, -1이 어떤 수인지 식별이 힘들기 때문에 #define을 이용해 None이라는 것으로 재정의해주어 사용했다.
calcul()이라는 함수를 하나 만들어 BFS탐색을 수행해주도록 만들었다.
탐색을 하면서 방문 처리와 거리를 기록하기 때문에 calcul을 하기 전에 다시 초기화를 해주어야 한다.
때문에 Clear()라는 함수를 만들어 방문처리와 거리를 기록하는 변수를 false와 0으로 초기화 해주도록 만들었다.
(calcul()함수를 실행하면 바로 Clear()를 호출하고, BFS를 수행하도록 짜는게 좋을 것 같다. 시간문제로 Clear를 외부에서 호출해주도록 짜져있다.)
또한 이미 TargetNum의 위치에 손이 위치해 있는 경우도 있기 때문에 calcul()함수에서 BFS를 시작할때, 예외처리를 해주었다.
(정확한 테스트 번호는 모르지만 13번 이후로 틀린 것이 많을 경우 해당 문제를 고려해볼만하다. => numbers로 [0, 0]을 전달하고, hand로 "right"를 전달해주면, 답은 [R,R]이 나와야 한다.)
코드를 너무 길게 짜서 시간이 오래걸렸다. 때문에 다른 사람의 코드를 보면서 짧고 빠르게 짜는 방법을 찾아 공부한 뒤 다시한번 정리를 해볼 예정이다.
실행 결과
