PS/프로그래머스
[카카오 인턴] 키패드 누르기 [V]
MQTT
2023. 7. 29. 02:01
https://school.programmers.co.kr/learn/courses/30/lessons/67256
설명:
키패드 영역에 누를 수 있는 손이 결정된다. 1,4,7은 왼손. 3,6,9는 오른손.
2,5,8,0 은 왼손과 오른손 중 주어진 값과의 차이가 어느 손이 작은지에 따라 작은값을 가진 손이 선택된다. 단 거리가 동일하면 주요한 손이 선택된다.
로직:
키패드 갯수가 0~9이므로 하드한 로직 구성.
1. 왼손 영역과 오른손 영역의 좌표들이 이미 정해져 있기에, 1,4,7이면 왼손으로 간주. 해당 좌표를 저장. 오른손 값인 3,6,9도 동일방식.
2. 2,5,8의 경우 왼손과 오른손 각각 2,5,8중 주어진 값의 위치와의 거리를 구한다.
3. 거리가 짧은 손을 선택한다.
4. 선택하지 않은 손은 기존(savingPoint) 좌표로 돌아간다. 선택된 손은 주어진 값 좌표를 설정한다.
#include<bits/stdc++.h>
using namespace std;
struct HandPoint { //왼손, 오른손 좌표 나타냄.
int y;
int x;
};
int getDist(const int& srcY, const int& srcX,const int& dstY, const int& dstX) {
int distanceX = abs(abs(dstX) - abs(srcX));
int distanceY = abs(abs(dstY) - abs(srcY));
return distanceY + distanceX;
}
string checkHand(const int& LeftDist,const int& RightDist, string MainHand) {
MainHand = MainHand == "right" ? "R" : "L";
if (LeftDist == RightDist) return MainHand; //거리차이 동일하면 주요 손으로.
return LeftDist < RightDist ? "L" : "R"; //left가 right보다 목적지까지의 거리가 작으면 left로. 아니면 right
}
string solution(vector<int> numbers, string hand) {
string answer = "";
HandPoint LeftPoint({ 3,0 }); // 초기 왼손의 위치 '*'에 위치함.
HandPoint RightPoint({ 3,2 }); // 초기 오른손의 위치 '#'에 위치함.
// 1,4,7과 3,6,9는 각 왼손, 오른손 영역임을 확정.
for (int num = 0; num < numbers.size(); ++num) {
//왼손 영역
if (numbers[num] == 1 || numbers[num] == 4 || numbers[num] == 7) {
switch (numbers[num]) {
case 1:
LeftPoint.y = 0;
LeftPoint.x = 0;
break;
case 4:
LeftPoint.y = 1;
LeftPoint.x = 0;
break;
case 7:
LeftPoint.y = 2;
LeftPoint.x = 0;
break;
}
answer += "L";
}
//오른손 영역
else if (numbers[num] == 3 || numbers[num] == 6 || numbers[num] == 9)
{
//오른손 위치 좌표 저장
switch (numbers[num]) {
case 3:
RightPoint.y = 0;
RightPoint.x = 2;
break;
case 6:
RightPoint.y = 1;
RightPoint.x = 2;
break;
case 9:
RightPoint.y = 2;
RightPoint.x = 2;
break;
}
answer += "R";
}
else {
//가운데 영역, 우선순위 1. 거리 순 2. 거리 동일하면 주요한 손으로 선택
//선택되지 않은 손의 좌표를 원상태로 백업하기 위한 용도.
HandPoint SavingPointL = LeftPoint;
HandPoint SavingPointR = RightPoint;
int LeftDistance;
int RightDistance;
switch (numbers[num])
{
case 0:
//왼손 좌표와 0의 좌표 3,1 간 거리
LeftDistance = getDist(LeftPoint.y, LeftPoint.x, 3, 1);
//오른손 좌표와 0의 좌표 3,1 간 거리
RightDistance = getDist(RightPoint.y, RightPoint.x, 3, 1);
//두 손 좌표 모두 0의 좌표로 임의로 설정. 향후 거리에 따라 그대로 3,1로 둘지 이전으로 돌아갈지 결정할 예정.
LeftPoint.y = 3;
LeftPoint.x = 1;
RightPoint.y = 3;
RightPoint.x = 1;
break;
case 2:
LeftDistance = getDist(LeftPoint.y, LeftPoint.x, 0, 1);
RightDistance = getDist(RightPoint.y, RightPoint.x, 0, 1);
LeftPoint.y = 0;
LeftPoint.x = 1;
RightPoint.y = 0;
RightPoint.x = 1;
break;
case 5:
LeftDistance = getDist(LeftPoint.y, LeftPoint.x, 1, 1);
RightDistance = getDist(RightPoint.y, RightPoint.x, 1, 1);
LeftPoint.y = 1;
LeftPoint.x = 1;
RightPoint.y = 1;
RightPoint.x = 1;
break;
case 8:
LeftDistance = getDist(LeftPoint.y, LeftPoint.x, 2, 1);
RightDistance = getDist(RightPoint.y, RightPoint.x, 2, 1);
LeftPoint.y = 2;
LeftPoint.x = 1;
RightPoint.y = 2;
RightPoint.x = 1;
break;
}
// 우선순위에 따라 손 선택.
string Hand = checkHand(LeftDistance, RightDistance, hand);
// 선택되지 않은 손은 백업.
Hand == "R" ? LeftPoint = SavingPointL : RightPoint = SavingPointR;
//asnwer에 선택된 손 추가.
answer += Hand;
}
}
return answer;
}
처음에 복잡한 로직을 구성했다. T/C 오히려 실패.
로직:
1. 1,4,7과 3,6,9는 하드코딩(정적)으로 위치값을 저장 및 L 또는 R표시
2. 2, 5, 8, 0이 주어진 값이라면 왼손과 오른손 좌표 지점으로부터 해당 주어진 값의 좌표간 거리가 가까운 손을 구해야한다.
-> 우선, 현재 위치를 저장한다. 그 다음 왼손 값과 오른손값 각각 주어진 값과 비교해 주어진값이 작으면 0행 방향쪽으로 상향으로 움직여야한다.
-> 주어진값이 더 크면 3행 방향쪽으로 하향한다. 다만, 0의 경우 맨 아래에 있기에 하향하는 쪽으로 간다.
-> 소프트코딩(동적)으로 방향배열을 활용해 현재위치 ry에 offset값을 주어 움직인다. 각각 주어진 값과 만나면 그 현재 위치를 갱신한다.
-> 왼손과 오른손의 이전위치에서 현재위치까지의 맨하탄 거리가 작은 손을 선택한다. 동일하면 주요한 손을 선택한다.
방향 배열 활용.
#include<bits/stdc++.h>
using namespace std;
/*
*
1. 1,4,7과 3,6,9는 하드코딩(정적)으로 위치값을 저장 및 L 또는 R표시
2. 2, 5, 8, 0이 주어진 값이라면 왼손과 오른손 좌표 지점으로부터 해당 주어진 값의 좌표간 거리가 가까운 손을 구해야한다.
-> 우선, 현재 위치를 저장한다. 그 다음 왼손 값과 오른손값 각각 주어진 값과 비교해 주어진값이 작으면 0행 방향쪽으로 상향으로 움직여야한다.
-> 주어진값이 더 크면 3행 방향쪽으로 하향한다. 다만, 0의 경우 맨 아래에 있기에 하향하는 쪽으로 간다.
-> 소프트코딩(동적)으로 방향배열을 활용해 현재위치 ry에 offset값을 주어 움직인다. 각각 주어진 값과 만나면 그 현재 위치를 갱신한다.
-> 왼손과 오른손의 이전위치에서 현재위치까지의 맨하탄 거리가 작은 손을 선택한다. 동일하면 주요한 손을 선택한다.
방향 배열 활용.
키패드 번호.
1 2 3
4 5 6
7 8 9
-1 0 -1 좌측 -1 : '*' , 우측 -1: '#' , 값이 0이면 무조건 내려가기.
자기보다 값이 위면 올라가고 아래면 내려가기. 그리고 현재 위치를 저장할 마스킹 배열 별도로 만듦.
distance 계산.
*/
//방향배열
int DirectArr[5][2]{
0,-1, //우 (오른손)
-1,0, // 하 (공용)
0,0, // 정자세 (공용)
1,0, // 상 (공용)
0,1, // 왼손
};
int DialNum[4][3]{ //키패드 번호
1, 2, 3,
4, 5, 6,
7, 8, 9,
-1,0, -1
};
int MaskArr[4][3]{ //디버깅용도, 왼/오른손 이동 후 좌표가 1로 표시됨.
0,0,0,
0,0,0,
0,0,0,
1,0,1
};
struct HandPoint { //왼손, 오른손 좌표 나타냄.
int y;
int x;
};
int getDist(int& ry, int& rx, const int n) { // ry, rx call by ref로 함수의 반환값이 distance, ry, rx임.
int distance = -1; //default.
//방향배열 활용해 DialNum의 현위치에서 값이 작으면 상향(0행방향) 또는 값이 크면 하향(3행방향. 단 값 0도 해당) 그리고 우측(왼손의 경우) 또는 좌측(오른손의 경우)으로 이동.
if (DialNum[ry][rx] <= n || n == 0) { // 하향식으로 탐색. n찾을 때 return. ( n이 0인 경우 하향식)
for (int y = ry; y < 4; ++y) { // 하향식이니 행이 올라감. ++
for (int t = 0; t < 5; ++t) {
int dy = y + DirectArr[t][0];
int dx = rx + DirectArr[t][1];
if (dy < 0 || dx < 0 || dy>3 || dx > 2)continue;
if (DialNum[dy][dx] == n) {
//맨하탄 거리
int distanceY = abs(abs(dy) - abs(ry));
int distanceX = abs(abs(dx) - abs(rx));
ry = dy; // 기존위치를 목적지인 현재 위치로 갱신.
rx = dx;
distance = distanceY + distanceX;
return distance;
}
}
}
}
else { //상향식으로 탐색
for (int y = ry; y >= 0; --y) { // 상향식이니 행이 내려감.
for (int t = 0; t < 5; ++t) {
int dy = y + DirectArr[t][0];
int dx = rx + DirectArr[t][1];
if (dy < 0 || dx < 0 || dy>3 || dx > 2)continue;
if (DialNum[dy][dx] == n) { //목적지 도착. //목적지 도착. '#' 와 '*'는 -1이니 자동으로 제외됨.
//맨하탄 거리
int distanceY = abs(abs(dy) - abs(ry));
int distanceX = abs(abs(dx) - abs(rx));
distance = distanceY + distanceX;
ry = dy; // 기존위치를 목적지인 현재 위치로 갱신.
rx = dx;
return distance;
}
}
}
}
return -1;
}
string checkHand(int LeftDist,int RightDist, string MainHand) {
if (LeftDist == -1) return "right";
if (RightDist == -1) return "left";
if (LeftDist == RightDist) return MainHand; //거리차이 동일하면 주요 손으로.
return LeftDist < RightDist ? "left" : "right"; //left가 right보다 목적지까지의 거리가 작으면 left로. 아니면 right
}
string solution(vector<int> numbers, string hand) {
string answer = "";
HandPoint LeftPoint({ 3,0 }); // 초기 왼손의 위치 '*'에 위치함.
HandPoint RightPoint({ 3,2 }); // 초기 오른손의 위치 '#'에 위치함.
// 1,4,7과 3,6,9는 각 왼손, 오른손 영역임을 확정.
for (int num = 0; num < numbers.size(); ++num) {
if (numbers[num] == 1 || numbers[num] == 4 || numbers[num] == 7) {
//MaskArr는 디버깅용도로 해당 손의 위치를 표시합니다.
// 기존 좌표 초기화.
MaskArr[LeftPoint.y][LeftPoint.x] = 0;
//왼손 위치 좌표 저장
switch (numbers[num]) {
case 1:
LeftPoint.y = 0;
LeftPoint.x = 0;
break;
case 4:
LeftPoint.y = 1;
LeftPoint.x = 0;
break;
case 7:
LeftPoint.y = 2;
LeftPoint.x = 0;
break;
}
//목적 좌표 표시
MaskArr[LeftPoint.y][LeftPoint.x] = 1;
answer += "L";
}
else if (numbers[num] == 3 || numbers[num] == 6 || numbers[num] == 9)
{
//MaskArr는 디버깅용도로 해당 손의 위치를 표시합니다.
// 기존 좌표 초기화.
MaskArr[RightPoint.y][RightPoint.x] = 0;
//오른손 위치 좌표 저장
switch (numbers[num]) {
case 3:
RightPoint.y = 0;
RightPoint.x = 2;
break;
case 6:
RightPoint.y = 1;
RightPoint.x = 2;
break;
case 9:
RightPoint.y = 2;
RightPoint.x = 2;
break;
}
//목적좌표 표시
MaskArr[RightPoint.y][RightPoint.x] = 1;
answer += "R";
}
else { // 2,5,8,0 인 가운데 위치한 번호 대상.
// 손 결정: 우선순위 ) 1.거리차이, 2.거리차이가 동일하면 주 손잡이로 결정.
//선택되지 않은 손의 좌표를 백업하기 위한 용도.
HandPoint SavingLeft = { LeftPoint.y, LeftPoint.x };
HandPoint SavingRight = { RightPoint.y, RightPoint.x};
// Left - Up/Down
//왼손좌표가 참조자형태로 바뀜.
int LeftDist = getDist(LeftPoint.y, LeftPoint.x, numbers[num]); //방향배열로 거리재기
// Right - Up/Down
//오른손좌표가 참조자형태로바뀜
int RightDist = getDist(RightPoint.y, RightPoint.x, numbers[num]); // 방향배열로 거리재기
//왼손 오른손 둘다 정답이 아닌 경우 예외처리함. 이런 경우는 존재하지 않는다고 생각하여 주석 .'
/*if (LeftDist == -1 && RightDist == -1)continue;*/
//둘 중 하나가 -1로 나오면 -1이 아닌 손을 선정. -1이란 왼손의 영역 또는 오른손의 영역이 아니라는 의미.
string HandResult = checkHand(LeftDist, RightDist, hand); // > , <, = 비교하여 어느 손에 해당하는지 결정하기.
// Answer이어붙이기.
if (HandResult == "right") {
LeftPoint.y = SavingLeft.y; // 왼손 위치 원상복귀
LeftPoint.x = SavingLeft.x;
//목적지 까지 잘 갔는지 확인 목적
MaskArr[SavingRight.y][SavingRight.x] = 0;
MaskArr[RightPoint.y][RightPoint.x] = 1;
answer += "R";
}
else {
RightPoint.y = SavingRight.y; // 오른손 위치 원상복귀
RightPoint.x = SavingRight.x;
//목적지 까지 잘 갔는지 확인 목적
MaskArr[SavingLeft.y][SavingLeft.x] = 0;
MaskArr[LeftPoint.y][LeftPoint.x] = 1;
answer += "L";
}
}
}
return answer;
}
int main(void) {
cout << solution({ 9,8,7,6,5,5,3,2,1,4 }, "right") << endl;
}