Level 1 키패드 누르기

시간 복잡도: O(N)

1#include <bits/stdc++.h>
2
3using namespace std;
4
5string solution(vector<int> numbers, string hand) {
6  string answer = "";
7  char _hand = hand[0]-32;
8  char numpad[4][3] = { {'1', '2', '3'}, 
9                    {'4', '5', '6'}, 
10                    {'7', '8', '9'},
11                    { '*', '0', '#'}};  
12  int l1 = 3, l2 = 0;
13  int r1 = 3, r2 = 2;
14
15  for(int n : numbers) {
16    if(n==0) n = 11;
17    int x1 = ((n-1)/3);
18    int x2 = (n-1)%3; 
19    int L = abs(x2-l2) + abs(x1-l1);
20    int R = abs(x2-r2) + abs(x1-r1);
21
22    if(n==1 || n==4 || n==7) {
23      answer += 'L';
24      l1 = x1;
25      l2 = x2;
26    } else if(n==3 || n==6 || n==9) {
27      answer += 'R';
28      r1 = x1;
29      r2 = x2;
30    } else { 
31      if(L == R) {
32        answer += _hand;
33        if(_hand=='R') r1=x1, r2=x2;
34        else l1=x1, l2=x2;
35      }else if(L < R) {
36        answer += 'L';
37        l1 = x1;
38        l2 = x2;
39      } else {
40        answer += 'R';
41        r1 = x1;
42        r2 = x2;
43      }
44    }
45  }
46
47  return answer;
48}

2차원 그래프에서 거리를 구하는 것처럼, 왼손과 오른손과 숫자의 거리를 구해서 더 가까운 쪽의 손을 사용하도록 했다.