프로그래머스] C++ 2020 카카오 인턴십 - 키패드 누르기(Level 1)

 

 

 

해당 문제는 프로그래머스 코딩테스트 연습에 있는 문제입니다.

아래 링크를 통해 풀 수 있습니다.

 

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

 

1. 조건

1. 왼손과 오른손이 있다. 왼손에 가까운 키페드는 1, 4, 7 이고, 오른손에 가까운 키패드는 3, 6, 9 이다.

2. 숫자가 주어질때, 왼손과 오른손을 사용해서 번호를 눌러야 하는데, 2, 5, 8, 0 숫자인 경우 현재 있는 손의 위치에서 가장 가까운 손으로 터치한다.

3. 만약 양손의 거리가 같다면 hand에 있는 손을 우선순위로 둔다.(오른손잡이, 왼손잡이)

 

2. 풀이

왼손과 오른손은 각각 1, 4, 7 과 3, 6, 9로 나뉘어서 해당 부분만 if문 처리해주면 쉽게 도출할 수 있습니다.

문제는 2, 5, 8, 0 입니다.

 

저는 해당 문제를 보고 처음에 bfs로 위치탐색을 진행할까 했는데, 코드가 너무 복잡해지고 이건 아닌것 같아서 다른 방법을 생각했습니다.

 

생각한 방법은 맨허튼 거리 구하기 공식을 사용한 것인데, 말만 거창하지 구하는 공식은 다음과 같습니다.

x1, y1과 x2, y2가 있다면 이 둘사이의 멘허튼 거리는 abs(x1 - x2) + abs(y1 - y2) 로 구할 수 있습니다.

 

해당 거리를 비교해서 가장 까까운 손으로 터치하는 식으로 문제를 풀면 쉽게 풀리는 문제입니다.

 

*, # 은 10과 11로 주었습니다.

 

3. 코드

#include <string>
#include <vector>

using namespace std;

vector<pair<int, int>> v = {
    {3, 1}, {0, 0}, {0, 1}, {0, 2},
    {1, 0}, {1, 1}, {1, 2},
    {2, 0}, {2, 1}, {2, 2},
    {3, 0}, {3, 2}
};

string solution(vector<int> numbers, string hand) {
    string answer = "";
    int left = 10;
    int right = 11;
    
    for( auto& n : numbers ) {
        if( n == 1 || n == 4 || n == 7 ) {
            answer += 'L';
            left = n;
        } else if( n == 3 || n == 6 || n == 9 ) {
            answer += 'R';
            right = n;
        } else {
            int left_locate = 
                abs(v[n].first - v[left].first) + abs(v[n].second - v[left].second);
            int right_locate = 
                abs(v[n].first - v[right].first) + abs(v[n].second - v[right].second);
            
            if( left_locate == right_locate ) {
                if( hand == "left" ) {
                    answer += 'L';
                    left = n;
                } else {
                    answer += 'R';
                    right = n;
                }
            } else if( left_locate < right_locate ) {
                answer += 'L';
                left = n;
            } else {
                answer += 'R';
                right = n;
            }
        }
    }
    
    return answer;
}