[2020 카카오 인턴십 코딩테스트] 키패드 누르기

분류 

시뮬레이션, bfs

 

요구사항

누르는 손가락 출력하기

 

풀이

1. 1, 4, 7 일때는 왼손으로 누른다

2. 3, 6, 9 일때는 오른손으로 누른다

3. 2, 5, 8, 0 일때는 왼손, 오른손으로 부터 target까지의 거리를 구해서 가까운 것을 선택한다

각각 동작마다 누른 손가락의 위치는 업데이트 시켜주어야 한다

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
struct go{
	int x;
	int y;
	int z;
};
int Lr=3;
int Lc=0;
int Rr=3;
int Rc=2;
int map[4][3]={
	1,2,3,
	4,5,6,
	7,8,9,
	10,0,11
};
int visit[4][3];
int dr[4] = {-1,0,1,0};
int dc[4] = {0,-1,0,1 };
go GetPos(int nownum){
	go temp;
	if(nownum==0){
		temp.x=3;
		temp.y=1;
	}
	else if(nownum==1){
		temp.x=0;
		temp.y=0;
	}
	else if(nownum==2){
		temp.x=0;
		temp.y=1;
	}
	else if(nownum==3){
		temp.x=0;
		temp.y=2;
	}
	else if(nownum==4){
		temp.x=1;
		temp.y=0;
	}
	else if(nownum==5){
		temp.x=1;
		temp.y=1;
	}
	else if(nownum==6){
		temp.x=1;
		temp.y=2;
	}
	else if(nownum==7){
		temp.x=2;
		temp.y=0;
	}
	else if(nownum==8){
		temp.x=2;
		temp.y=1;
	}
	else if(nownum==9){
		temp.x=2;
		temp.y=2;
	}
	return temp;
}
int GetDist(int r, int c, int nownum){
	memset(visit,0,sizeof(visit));
	visit[r][c]=1;
	go temp;
	temp.x=r;
	temp.y=c;
	temp.z=0;
	queue<go> q;
	q.push(temp);
	if(map[r][c]==nownum) return 0;
	while(!q.empty()){
		int nowr= q.front().x;
		int nowc= q.front().y;
		int dist=q.front().z;
		q.pop();
		for(int i=0 ; i<4 ; i++){
			int nr = nowr+dr[i];
			int nc = nowc+dc[i];
			if(nr<0 || nc<0 || nr>=4 || nc>=3) continue;
			if(visit[nr][nc]==1) continue;
			if(map[nr][nc]== 10 || map[nr][nc]==11) continue;
			if(map[nr][nc]==nownum){
				return dist+1;
			}
			visit[nr][nc]=1;
			q.push({nr,nc,dist+1});
		}
	}	
}
void updata_pos(int& r, int& c, int nownum){
	go temp;
	temp=GetPos(nownum);
	r=temp.x;
	c=temp.y;
}
string solution(vector<int> numbers, string hand) {
    string answer = "";
	int cnt=0;
	int flag=0;
	for(auto i: numbers){
		int nownum = i;
		if(nownum ==1 ||nownum ==4 ||nownum ==7 )	{
			updata_pos(Lr,Lc,nownum);
			answer+='L';
		}
		else if(nownum==3 || nownum ==6 || nownum==9) {
			updata_pos(Rr,Rc,nownum);
			answer+='R';
		}
		else{
			int Ldist = GetDist(Lr, Lc, nownum);
			int Rdist = GetDist(Rr,Rc,nownum);
			if(Ldist < Rdist){
				updata_pos(Lr,Lc,nownum);
				answer+='L';
			}
			else if(Rdist < Ldist){
				updata_pos(Rr,Rc,nownum);
				answer+='R';
			}
			else if(Rdist == Ldist){
				if(hand=="left"){
					updata_pos(Lr,Lc,nownum);
					answer+='L';
				}
				else if(hand=="right"){
					updata_pos(Rr,Rc,nownum);
					answer+='R';
				}
			}
		}
	}
	
    return answer;
}