[C_C++]코딩테스트 연습/[프로그래머스] level 1
[C++] 프로그래머스 - 키패드 누르기 (배열 노가다 + 지향할 풀이)
코딩굼벵이
2021. 6. 25. 15:14
728x90
문제
내 풀이
풀이 방법 )
- 1, 4, 7 : L
- 3, 6, 9 : R
- 2, 5, 8, 0 :
① 엄지 거리 - 가까운 손 (dist가 더 작은 것)
② 거리 같을 때 - 왼손잡이냐 오른손잡이냐
- 거리 : 각 키패드 번호에서 각 번호까지의 거리를 담은 배열들을 선언했다.
배열의 인덱스가 0부터 시작하는 점을 이용해 각 자리까지의 거리를 각 인덱스 자리에 맞게 넣었다. - 현재 위치 : 왼손 위치는 left, 오른손 위치는 right에 담고 초기 위치를 -1로 설정했다.
- 눌러야할 키패드가 2,5,8,0일 때만 거리와 왼손/오른손잡이 여부를 생각한다.
왼손/오른손의 현재 위치를 받아 각각에 대한 switch 문을 실행한다.
현재 위치에 따라 미리 만들어뒀던 키패드 자리의 거리배열을 선택하여 눌러야할 번호(numbers[i])를 인덱스로 넣어 불러와 L/Rdist에 현재위치로부터 눌러야할 번호까지의 거리를 넣는다.
거리를 비교해 짧은 것을 사용하고, 거리가 같은 경우 왼손잡이/오른손잡이 여부를 보고 결정한다.
#include <string>
#include <vector>
using namespace std;
string solution(vector<int> numbers, string hand) {
string answer = "";
// 왼손/오른손 여부
int left = -1, right = -1;
int Ldist = 0, Rdist = 0;
//거리
int Lstart[10] = { 1,3,4,5,2,3,4,1,2,3 };
int Rstart[10] = { 1,5,4,3,4,3,2,3,2,1 };
int k0[10] = { 0,4,3,4,3,2,3,2,1,2 };
int k1[10] = { 4,0,1,2,1,2,3,2,3,4 };
int k2[10] = { 3,1,0,1,2,1,2,3,2,3 };
int k3[10] = { 4,2,1,0,2,2,1,4,3,2 };
int k4[10] = { 3,1,2,3,0,1,2,1,2,3 };
int k5[10] = { 2,2,1,2,1,0,1,2,1,2 };
int k6[10] = { 3,3,2,1,2,1,0,3,2,1 };
int k7[10] = { 2,2,3,4,1,2,3,0,1,2 };
int k8[10] = { 1,3,2,3,2,1,2,1,0,1 };
int k9[10] = { 2,4,3,2,3,2,1,2,1,0 };
for (int i = 0; i < numbers.size(); i++) {
if (numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7) {
answer.push_back('L');
left = numbers[i];
}
else if (numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9){
answer.push_back('R');
right = numbers[i];
}
else { //2,5,8,0
switch (left)
{
case -1:
Ldist = Lstart[numbers[i]];
break;
case 0:
Ldist = k0[numbers[i]];
break;
case 1:
Ldist = k1[numbers[i]];
break;
case 2:
Ldist = k2[numbers[i]];
break;
case 3:
Ldist = k3[numbers[i]];
break;
case 4:
Ldist = k4[numbers[i]];
break;
case 5:
Ldist = k5[numbers[i]];
break;
case 6:
Ldist = k6[numbers[i]];
break;
case 7:
Ldist = k7[numbers[i]];
break;
case 8:
Ldist = k8[numbers[i]];
break;
case 9:
Ldist = k9[numbers[i]];
break;
default:
break;
}
switch (right)
{
case -1:
Rdist = Rstart[numbers[i]];
break;
case 0:
Rdist = k0[numbers[i]];
break;
case 1:
Rdist = k1[numbers[i]];
break;
case 2:
Rdist = k2[numbers[i]];
break;
case 3:
Rdist = k3[numbers[i]];
break;
case 4:
Rdist = k4[numbers[i]];
break;
case 5:
Rdist = k5[numbers[i]];
break;
case 6:
Rdist = k6[numbers[i]];
break;
case 7:
Rdist = k7[numbers[i]];
break;
case 8:
Rdist = k8[numbers[i]];
break;
case 9:
Rdist = k9[numbers[i]];
break;
default:
break;
}
if (Ldist < Rdist) {
answer.push_back('L');
left = numbers[i];
}
else if (Ldist > Rdist) {
answer.push_back('R');
right = numbers[i];
}
else {
if (hand == "left") { answer.push_back('L'); left = numbers[i]; }
else { answer.push_back('R'); right = numbers[i]; }
}
}
}
return answer;
}
나쁜 점 )
2,5,8,0을 눌렀을 때만 거리를 고려하면 되는데 모든 키패드에서 누른번호까지의 거리를 고려하느라 쓸데없이 배열을 많이 만들었다. 또 수학적으로 접근하지 않아 만들지 않아도 되는 배열을 너무 많이 만들었다. 즉, 메모리 낭비가 심하다.
좋은 점 ) 빠르다.
지향하려는 풀이 )
2,5,8,0이 들어왔을 시에 현재 위치에서 거리를 구하는 규칙을 찾는다.
위치의 편의상 *, # 을 각각 10, 12 로 두고 계산을 한다.
(현재 위치) - (누르려는 번호) 의 절댓값을 Temp로 두고 다룬다. 한줄이 넘어가면 거리가 하나 늘어나므로 Temp를 3으로 나눈 몫과 나머지를 더한 Temp/3 + Temp%3이 거리가 된다.
#include <string>
#include <vector>
#include <math.h>
using namespace std;
string solution(vector<int> numbers, string hand) {
string answer = "";
int left = 10, right = 12;
int Ltemp, Rtemp, Ldist, Rdist;
for (int i = 0; i < numbers.size(); i++) {
if (numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7) {
answer += 'L';
left = numbers[i];
}
else if (numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9) {
answer += 'R';
right = numbers[i];
}
else { //2,5,8,0
if (numbers[i] == 0) numbers[i] = 11;
int Ltemp = abs(left - numbers[i]);
int Rtemp = abs(right - numbers[i]);
Ldist = (Ltemp / 3) + (Ltemp % 3);
Rdist = (Rtemp / 3) + (Rtemp % 3);
if (Ldist < Rdist) {
answer += 'L';
left = numbers[i];
}
else if (Ldist > Rdist) {
answer += 'R';
right = numbers[i];
}
else {
if (hand == "left") { answer += 'L'; left = numbers[i]; }
else { answer += 'R'; right = numbers[i]; }
}
}
}
return answer;
}