programmers 키패드 누르기

programmers 키패드 누르기 : programmers.co.kr/learn/courses/30/lessons/67256

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

2020 카카오 인턴십에서 출제된 키패드 누르기 입니다.

문제에서 요구하는 대로 구현할 수 있는지 묻는 문제이며,

노가다해도되지만 귀찮아서 bfs로 탐색하였습니다.

 

설명할 부분이 따로 없다고 생각되어서 간단히 코드만 첨부하겠습니다..

길긴하지만 간단하기 때문에 코드 읽어보시면 충분히 이해하실거라 생각합니다. 

 

#include <string>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

struct point{
  int y, x, cnt;  
};
int arr[4][3] = {{10,2,10},{10,5,10},{10,8,10},{10,0,10}};
int my[4] = {-1,1,0,0};
int mx[4] = {0,0,1,-1};
bool visit[4][3];

// 2,5,8,0 부분에 대한 bfs
int findMinKey(int y, int x, int key){
    queue<point> q;
    memset(visit, false, sizeof(visit));
    q.push({y,x,0});
    while(!q.empty()){
        int y = q.front().y;
        int x = q.front().x;
        int cnt = q.front().cnt;
        q.pop();
        
        if(arr[y][x] == key) return cnt;
        if(visit[y][x]) continue;
        visit[y][x] = true;
        for(int i = 0; i<4; i++){
            int yy = y+my[i];
            int xx = x+mx[i];
            if(yy>=0&&yy<4&&xx>=0&&xx<3&&!visit[yy][xx]) q.push({yy,xx,cnt+1});
        }
    }
}

string solution(vector<int> numbers, string hand) {
    string answer = "";
    
    pair<int,int> left = {3,0};
    pair<int,int> right = {3,2};
    for(auto key : numbers){
        if(key == 1 || key == 4 || key == 7){
            answer += 'L';
            if(key == 1) left = {0,0};
            if(key == 4) left = {1,0};
            if(key == 7) left = {2,0};
        }
        else if(key == 3 || key == 6 || key == 9){
            answer += 'R';
            if(key == 3) right = {0,2};
            if(key == 6) right = {1,2};
            if(key == 9) right = {2,2};
        }
        else{
            int moveCntL = findMinKey(left.first, left.second, key);
            int moveCntR = findMinKey(right.first, right.second, key);
            if(moveCntL == moveCntR){
                if(hand.compare("left") == 0){
                    answer += 'L';
                    if(key == 2) left = {0,1};
                    if(key == 5) left = {1,1};
                    if(key == 8) left = {2,1};
                    if(key == 0) left = {3,1};
                }
                else{
                    answer += 'R';
                    if(key == 2) right = {0,1};
                    if(key == 5) right = {1,1};
                    if(key == 8) right = {2,1};
                    if(key == 0) right = {3,1};
                }
            }
            else if(moveCntL < moveCntR){
                answer += 'L';
                if(key == 2) left = {0,1};
                if(key == 5) left = {1,1};
                if(key == 8) left = {2,1};
                if(key == 0) left = {3,1};
            }
            else{
                answer += 'R';
                if(key == 2) right = {0,1};
                if(key == 5) right = {1,1};
                if(key == 8) right = {2,1};
                if(key == 0) right = {3,1};
            }
        }
    }
    
    return answer;
}