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

전형적인 시간은 오래잡아먹고 맞춰도 테케만 맞춘거같은 느낌의 문제...

무조건 또 풀어봐야한다.  

난이도 Lv1 라고 하지만 Lv2 이상인 것 같다.

문제

입출력

문제해석

 

다음과 같은 숫자 다이얼에서 각각 왼손/오른손 엄지로 누르는 최적의 위치 탐색(BFS)

 

 

실패코드 

우선 풀면서도 너무 헷갈리게 품... 흐름을 놓치면 첨부터 보느라 시간너무 잡아먹음

너무 알고리즘 보단 하드코딩 느낌으로 품 (시간소모 심하고, 효율성 떨어짐)

간과한점

• 해당문제는 번호판의 배열이 총 12개로 한정적이기때문에 번호판의 좌표를 배열에 넣어야한다.
• 또한 바둑판 최단거리등이 나올때 dfs/bfs으로 접근하려는 선입견X
• (x,y) -> (a,b) 지점 사이의 거리의 로직을 생각

#include <string>
#include <queue>
#include <iostream>
using namespace std;

int cal[] = { -3, +1, +3, -1 };//위, 오, 아, 왼
int locLeft = 10;
int locRight= 12;
 
string solution(vector<int> numbers, string hand) 
{

	string answer = "";

	for (int i = 0; i < numbers.size(); i++)
	{
		if (numbers[i] == 0)
			numbers[i] = 11;
		if (numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7)
		{
			locLeft = numbers[i];
			answer += "L"; 
		}
		else if (numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9)
		{
			locRight = numbers[i];
			answer += "R";
		}
		//numbers[i] == 0 이면 11이다.
		else
		{
			int cntL = 1;
			int cntR = 1;
			int comL;
			int comR;
			bool visit[12] = { false, };
			bool visit2[12] = { false, };
			queue<int> q;
			queue<int> q2;

			q.push(locRight);
			q2.push(locLeft);

		
			while (!q.empty())
			{
				int ex =0;
				int x = q.front();
				visit[x] = true;
				q.pop();
				for (int w = 0; w < 4; w++)
                {
					int dx = x + cal[w];
					if (visit[dx] == true)
						continue;

					//예외처리 1) 1,4,7,11 왼쪽불가 2)1,2,3 위로불가 , (3) 3,6,9,12 오불가 , (4) 10,11,12아래로 불가 
					if (w == 1 && (dx == 4 || dx == 7 || dx == 10 || dx == 13))
						continue;
					if (w == 0 && (dx == 0 || dx == 1))//위로
						continue;
					//아래
					if (w == 2 && dx == 14 || dx == 15)
						continue;
					
					if (dx == 1 || dx == 4 || dx + cal[w] == 7)
						continue; 

					q.push(dx);
					visit[dx] = true;

					if (dx == numbers[i])
					{
						ex = 1;
						comR = cntR+1;
						break;
					}
				
				}
				if (ex == 1)
				{
					break;
				}
				cntR++;

			}
			while (!q2.empty())
			{
				int ex=0;
				int x = q2.front();
				visit2[x] = true;
				q2.pop();
				for (int w = 0; w < 4; w++)
				{
					int dx = x + cal[w];
					if (visit2[dx] == true)
						continue;
					//예외처리 1) 1,4,7,11 왼쪽불가 2)1,2,3 위로불가 , (3) 3,6,9,12 오불가 , (4) 10,11,12아래로 불가 
					if (w == 3 && (dx == 0 || dx == 3 || dx == 6 || dx == 9))
						continue;
					if (w == 0 && (dx == -2 || dx == -1))//위로
						continue;
					if (w == 2 && dx == 13 || dx == 14)
						continue;
					if (dx == 3 || dx == 6 || dx == 9)
						continue;
					
					q2.push(dx);
					visit2[dx] = true;
					if (dx== numbers[i])
					{
						comL = cntL+1;
						ex = 1;
						break;
					}

				}

				if (ex == 1)
				{
					break;
				}
				cntL++;
			}

			if (comL < comR)
			{
				answer += "L";
				locLeft = numbers[i];

			}
			else if (comL > comR)
			{
				answer += "R";
				locRight = numbers[i];
			}
			else
			{
				if (hand == "right")
				{
					answer += "R";
					locRight = numbers[i];
				}
				else
				{
					answer += "L";
					locLeft = numbers[i];
				}
			}
		}
	}


	return answer;
 

}

 

Sol 코드

우선 현지점 목표지점까지 거리는 (x,y) -> (a,b)  절대값(x-a) + (y-n) 이다.

우선 각 번호의 좌표배열을 만들고 목표지점과의 거리를 구하는 로직을 구현함.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int locLeft = 10;
int locRight = 11;
pair<int, int> ar[12] = { { 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)
{
	//solution({ 7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2 }, "left");
	string answer = "";

	for (int i = 0; i < numbers.size(); i++)
	{
		if (numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7)
		{
			locLeft = numbers[i];
			answer += "L";
		}
		else if (numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9)
		{
			locRight = numbers[i];
			answer += "R";
		}
		//numbers[i] == 0 이면 11이다.
		else
		{
			int leftmax = abs(ar[numbers[i]].first - ar[locLeft].first) + abs(ar[numbers[i]].second - ar[locLeft].second);
			int rightmax = abs(ar[numbers[i]].first - ar[locRight].first) + abs(ar[numbers[i]].second - ar[locRight].second);
			if (leftmax > rightmax)
			{
				locRight = numbers[i];
				answer += "R";
			}
			else if (leftmax < rightmax)
			{
				locLeft = numbers[i];
				answer += "L";
			}
			else if (leftmax == rightmax)
			{
				if (hand == "right")
				{
					locRight = numbers[i];
					answer += "R";
				}
				else
				{
					locLeft = numbers[i];
					answer += "L";
				}
			}
		}
	}

	return answer;
}

int main()
{

	//solution({ 1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5 }, "right");
	solution({ 7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2 }, "left");
	return 0;
}