[프로그래머스] 키패드 누르기

https://programmers.co.kr/learn/courses/30/lessons/67256

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

---

 

-풀이-

단순 구현 문제이다. 키패드 각 숫자를 아래의 인덱스를 갖도록 설정해준다.

1 {0,0}	2 {0,1}	3 {0,2}
4 {1,0}	5 {1,1}	6 {1,2}
7 {2,0}	8 {2,1}	9 {2,2}
10(*) {3,0}	0 {3,1}	11(#) {3,2}

 

먼저, 왼손 또는 오른손이 현재 있는 버튼의 인덱스를 반환해주는 함수이다. 시간복잡도 O(1)

pair<int,int> get_index(int number){
    switch(number){
        case 1:
            return {0,0};
        case 2:
            return {0,1};
        case 3:
            return {0,2};
        case 4:
            return {1,0};
        case 5:
            return {1,1};
        case 6:
            return {1,2};
        case 7:
            return {2,0};
        case 8:
            return {2,1};
        case 9:
            return {2,2};
        case 0:
            return {3,1};
        case 10:
            return {3,0};
        case 11:
            return {3,2};
    }
}

 

그다음으로는, 2,5,8,0 을 누르기 위해서는 , 해당 번호와 왼손,오른손이 있는 버튼의 거리를 알아야 한다. 그 거리를 반환해 주는 함수이다. 시간복잡도 O(1)

int get_distance(int now,int goal){
    pair<int,int> cur,to;
    cur=get_index(now);
    to=get_index(goal);
    return abs(cur.first-to.first)+abs(cur.second-to.second);
}

 

이것을 이용해서, 다음 누를 버튼이 1,4,7이라면 answer에 L을 추가해준 뒤, 왼손이 있는 버튼을 갱신한다.

다음 누를버튼이 3,6,9라면 answer에 R을 추가해준 뒤, 오른손이 있는 버튼을 갱신해준다.

다음 누를 버튼이 2,5,8,0 이라면, 위의 get_distance 함수를 이용하여, 왼손과 버튼의 거리, 오른손과 버튼의 거리를 구해준뒤, 더 짧은곳을 옮겨주어 갱신해준다. 이때 거리가 같다면 , 어느손잡인지를 체크해주고 갱신해준다.

 

-시간복잡도-

위의 함수들은 모두 O(1)이 걸린다. 따라서 numbers의 길이를 N이라고 한다면, 시간복잡도는 O(N)이 된다.

 

-코드-

 

#include <string>
#include <vector>
#include<cmath>
using namespace std;

pair<int,int> get_index(int number){
    switch(number){
        case 1:
            return {0,0};
        case 2:
            return {0,1};
        case 3:
            return {0,2};
        case 4:
            return {1,0};
        case 5:
            return {1,1};
        case 6:
            return {1,2};
        case 7:
            return {2,0};
        case 8:
            return {2,1};
        case 9:
            return {2,2};
        case 0:
            return {3,1};
        case 10:
            return {3,0};
        case 11:
            return {3,2};
    }
}

int get_distance(int now,int goal){
    pair<int,int> cur,to;
    cur=get_index(now);
    to=get_index(goal);
    return abs(cur.first-to.first)+abs(cur.second-to.second);
}

string solution(vector<int> numbers, string hand) {
    string answer = "";
    int lnow,rnow;
    lnow=10;//현재위치 *
    rnow=11;//현재위치 #

    
    for(int i=0;i<numbers.size();i++){
        int next=numbers[i];
        if(next==1||next==4||next==7){
            answer+="L";
            lnow=next;
        }
        else if(next==3||next==6||next==9){
            answer+="R";
            rnow=next;
        }
        else{
            int lgap=get_distance(lnow,next);
            int rgap=get_distance(rnow,next);
            if(lgap<rgap){
                answer+="L";
                lnow=next;
            }
            else if(lgap>rgap){
                answer+="R";
                rnow=next;
            }
            else{
                if(hand=="left"){
                    answer+="L";
                    lnow=next;
                }
                else{
                    answer+="R";
                    rnow=next;
                }
            }
        }
    }
    return answer;
}