(프로그래머스 C++) 키패드 누르기

문제 링크 : programmers.co.kr/learn/courses/30/lessons/67256

코딩테스트 연습 - 키패드 누르기

문제 풀이는 다음과 같다.

1. 1,4,7번을 선택하는 경우와 3,6,9를 선택하는 경우는 답이 정해져있으므로 그대로 구현해주면 된다.

2. 문제는 2,5,8,0을 선택하는 과정이다. 현재 왼손의 위치와 오른손의 위치와 목표 다이얼을 비교하여 가까운 값만 저장해야하기 때문이다.

먼저 int형 4*3 배열 을 만들어 준뒤, 키 패드와 똑같은 값들을 입력해준다. 

이때 *와 #에는 본인이 원하는 임의의 값을 넣어줘도 된다.

3. 이때 시작 다이얼 지점이 *와 #임을 주의하자. 무턱대고 0과같은 임의의 값을 넣었다가는 실패하고 만다.

4. 목표 다이얼이 2,5,8,0일 경우, 왼손과 오른쪽의 다이얼 위치(i,j), (i2,j2)를 목표다이얼의 위치(i3,j3)와 비교해서 가까운 값으로 저장해준다.

#include <string>
#include <vector>

using namespace std;

int keys[4][3] = {1,2,3,4,5,6,7,8,9,100,0,101};

string solution(vector<int> numbers, string hand) {
    string answer = "";
    int le = 100, ri = 101; // 최초의 위치가 *과 #임을 기억하자!
    for(int i : numbers){
        if(i==1||i==4||i==7){
            answer += 'L';
            le = i;
        }
        else if(i==2||i==5||i==8||i==0){
            int temp_le = 0, temp_ri = 0;
            pair<int,int> temp_now;
            for(int a=0; a<4; a++){
                for(int b=0; b<3; b++){
                    if(keys[a][b]==i) {
                        temp_now.first = a, temp_now.second = b;
                        break;
                    }
                }
            }
            for(int a=0; a<4; a++){
                for(int b=0; b<3; b++){
                    if(keys[a][b]==le) temp_le= abs(a-temp_now.first) + abs(b-temp_now.second);
                    if(keys[a][b]==ri) temp_ri= abs(a-temp_now.first) + abs(b-temp_now.second);
                }
            }
            if(temp_le<temp_ri){
                le = i;
                answer += 'L';
            }
            else if(temp_le>temp_ri){
                ri = i;
                answer += 'R';
            }
            else{
                if(hand=="left"){
                    answer += 'L';
                    le = i;
                }
                else{
                    answer += 'R';
                    ri = i;
                }
            }
        }
        else{ // 맨 오른쪽 라인
            answer += 'R';
            ri = i;
        }
    }
    return answer;
}

정확성 테스트

테스트 1 〉	통과 (0.01ms, 3.97MB)
테스트 2 〉	통과 (0.01ms, 3.98MB)
테스트 3 〉	통과 (0.01ms, 3.96MB)
테스트 4 〉	통과 (0.01ms, 3.78MB)
테스트 5 〉	통과 (0.01ms, 3.98MB)
테스트 6 〉	통과 (0.01ms, 3.84MB)
테스트 7 〉	통과 (0.01ms, 3.97MB)
테스트 8 〉	통과 (0.01ms, 3.84MB)
테스트 9 〉	통과 (0.01ms, 3.92MB)
테스트 10 〉	통과 (0.02ms, 3.97MB)
테스트 11 〉	통과 (0.01ms, 3.95MB)
테스트 12 〉	통과 (0.02ms, 3.95MB)
테스트 13 〉	통과 (0.01ms, 3.96MB)
테스트 14 〉	통과 (0.02ms, 3.77MB)
테스트 15 〉	통과 (0.02ms, 3.98MB)
테스트 16 〉	통과 (0.02ms, 3.96MB)
테스트 17 〉	통과 (0.04ms, 3.98MB)
테스트 18 〉	통과 (0.03ms, 3.94MB)
테스트 19 〉	통과 (0.04ms, 3.98MB)
테스트 20 〉	통과 (0.04ms, 3.98MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0

---

빨리푸는것에만 초점을 맞추다보니 정답은 나왔지만 무턱대고 3중 for문이 구현되어 만족스럽지 못했다. 

그러다 스터디원 분들이 map으로 풀어낸 것을 발견하고 그것을 참고해서 풀어봤다.

 

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

int keys[4][3] = {
    1,2,3,
    4,5,6,
    7,8,9,
    100,0,101
};

unordered_map<int, pair<int,int>> m;
int dis(int ny, int nx, int dy, int dx){
    return abs(ny-dy) + abs(nx-dx);
}

string solution(vector<int> numbers, string hand) {
    string answer = "";
    for(int i=0; i<4; i++){
        for(int j=0; j<3; j++){
            m[keys[i][j]] = {i,j};
        }
    }
    int le = 100, ri = 101; // 최초의 위치가 *과 #임을 기억하자!
    for(int i : numbers){
        if(i==1||i==4||i==7){ // 맨 왼쪽 라인
            answer += 'L';
            le = i;
        }
        else if(i==2||i==5||i==8||i==0){ // 가운데 라인
            int new_left = dis(m[i].first, m[i].second, m[le].first, m[le].second);
            int new_right = dis(m[i].first, m[i].second, m[ri].first, m[ri].second);
            if(new_left>new_right){
                ri = i;
                answer += 'R';
            }
            else if(new_left<new_right){
                le = i;
                answer += 'L';
            }
            else{
                if(hand=="left"){
                    le = i;
                    answer += 'L';
                }
                else{
                    ri = i;
                    answer += 'R';
                }
            }
        }
        else{ // 맨 오른쪽 라인
            answer += 'R';
            ri = i;
        }
    }
    return answer;
}

정확성 테스트

테스트 1 〉	통과 (0.01ms, 3.96MB)
테스트 2 〉	통과 (0.02ms, 3.97MB)
테스트 3 〉	통과 (0.02ms, 3.97MB)
테스트 4 〉	통과 (0.01ms, 3.89MB)
테스트 5 〉	통과 (0.01ms, 3.95MB)
테스트 6 〉	통과 (0.01ms, 3.96MB)
테스트 7 〉	통과 (0.02ms, 3.83MB)
테스트 8 〉	통과 (0.02ms, 3.96MB)
테스트 9 〉	통과 (0.02ms, 3.93MB)
테스트 10 〉	통과 (0.02ms, 3.97MB)
테스트 11 〉	통과 (0.02ms, 3.84MB)
테스트 12 〉	통과 (0.02ms, 3.93MB)
테스트 13 〉	통과 (0.02ms, 3.97MB)
테스트 14 〉	통과 (0.03ms, 3.95MB)
테스트 15 〉	통과 (0.04ms, 3.96MB)
테스트 16 〉	통과 (0.03ms, 3.96MB)
테스트 17 〉	통과 (0.06ms, 3.95MB)
테스트 18 〉	통과 (0.06ms, 3.96MB)
테스트 19 〉	통과 (0.06ms, 3.9MB)
테스트 20 〉	통과 (0.06ms, 3.95MB)

코드 자체는 깔끔했지만 되려 시간이 더 오래걸렸다.

아마 키패드의 값이 적은 값으로 주어져서, 오히려 map을 쓰는게 더 많은 시간이 요구되었나보다.