키패드 누르기

Posted on Edited on In , ,

문제정의

키패드를 어느 쪽 손으로 눌러야 하는 가에 대한 문제이다. 초기 왼손의 위치는 *에 오른손의 위치는 #에 위치해있다. 1,4,7은 무조건 왼손으로 누르고 3,6,9는 오른손으로 누른다. 손가락은 상하좌우로만 움직일 수 있다. 2,5,8,0은 왼손과 오른손 중 더 가까이 있는 손가락으로 누르며, 만약 두 손가락이 움직이는 거리가 같은 경우 주로 쓰는 손으로 누른다. 눌러야할 번호들이 주어지면 어느쪽 손으로 누르는지 "L"과 "R"로 구성된 문자열로 나타내라.



## 문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class KeyPad {

    public static void main(String[] args)
    {
        int[] numbers = {1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5};
        String hand = "right";

        StringBuilder buff = new StringBuilder();
        int left_pos = 10, right_pos = 11;
        boolean isleft = false;
        int[][] moves = {
            {0, -1, 3, -1, -1, 2, -1, -1, 1, -1}, //0
            {4, -1, 1, -1, -1, 2, -1, -1, 3, -1}, //1
            {3, -1, 0, -1, -1, 1, -1, -1, 2, -1}, //2
            {4, -1, 1, -1, -1, 2, -1, -1, 3, -1}, //3
            {3, -1, 2, -1, -1, 1, -1, -1, 2, -1}, //4
            {2, -1, 1, -1, -1, 0, -1, -1, 1, -1}, //5
            {3, -1, 2, -1, -1, 1, -1, -1, 2, -1}, //6
            {2, -1, 3, -1, -1, 2, -1, -1, 1, -1}, //7
            {1, -1, 2, -1, -1, 1, -1, -1, 0, -1}, //8
            {2, -1, 3, -1, -1, 2, -1, -1, 1, -1}, //9
            {1, -1, 4, -1, -1, 3, -1, -1, 2, -1}, //10(*)
            {1, -1, 4, -1, -1, 3, -1, -1, 2, -1} //11(#)
        };
        
        for(int num : numbers)
        {
            if(num == 1 || num == 4 || num == 7)
                isleft = true;
            else if(num == 3 || num == 6 || num == 9)
                isleft = false;
            else
            {
                int left_dist = moves[left_pos][num];
                int right_dist = moves[right_pos][num];
                if(left_dist < right_dist)
                    isleft = true;
                else if(right_dist < left_dist)
                    isleft = false;
                else
                {
                    if(hand.equals("left"))
                        isleft = true;
                    else
                        isleft = false;
                }
            }
            if(isleft)
            {
                buff.append("L");
                left_pos = num;
            }
            else
            {
                buff.append("R");
                right_pos = num;
            }
        }
        
        String answer = buff.toString();
        System.out.print(answer);
    }
    
}
부분부분 보도록 하자 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
StringBuilder buff = new StringBuilder();
int left_pos = 10, right_pos = 11;
boolean isleft = false;
int[][] moves = {
    {0, -1, 3, -1, -1, 2, -1, -1, 1, -1}, //0
    {4, -1, 1, -1, -1, 2, -1, -1, 3, -1}, //1
    {3, -1, 0, -1, -1, 1, -1, -1, 2, -1}, //2
    {4, -1, 1, -1, -1, 2, -1, -1, 3, -1}, //3
    {3, -1, 2, -1, -1, 1, -1, -1, 2, -1}, //4
    {2, -1, 1, -1, -1, 0, -1, -1, 1, -1}, //5
    {3, -1, 2, -1, -1, 1, -1, -1, 2, -1}, //6
    {2, -1, 3, -1, -1, 2, -1, -1, 1, -1}, //7
    {1, -1, 2, -1, -1, 1, -1, -1, 0, -1}, //8
    {2, -1, 3, -1, -1, 2, -1, -1, 1, -1}, //9
    {1, -1, 4, -1, -1, 3, -1, -1, 2, -1}, //10(*)
    {1, -1, 4, -1, -1, 3, -1, -1, 2, -1} //11(#)
};
정답을 담을 StringBuilder buff를 선언한다. 초기 왼손은 *에 있고 오른손은 #에 있을때 이를 각각 10과 11로 지정한다. 그리고 moves를 작성한다. 번거로울 수 있지만, 마땅한 식이 떠오르지 않을 때 빠르게 문제를 풀 수 있다. 행이 시작점을 나타내고 열을 끝나는 점이라고 했을 때, 움직이는 횟수를 기록하였다. 예를들면 1에서 0으로 가기까지는 moves[1][0]에 해당하는 수이므로 4가 된 것을 볼 수 있다. 다음으로 boolean값에 해당하는 isleft를 선언한다. 이는 왼손으로 키패드를 눌러야하는지 나타내는 변수로 초기화는 아무렇게나 해도 상관없다. 필자는 false로 초기화하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
for(int num : numbers)
{
    if(num == 1 || num == 4 || num == 7)
        isleft = true;
    else if(num == 3 || num == 6 || num == 9)
        isleft = false;
    else
    {
        int left_dist = moves[left_pos][num];
        int right_dist = moves[right_pos][num];
        if(left_dist < right_dist)
            isleft = true;
        else if(right_dist < left_dist)
            isleft = false;
        else
        {
            if(hand.equals("left"))
                isleft = true;
            else
                isleft = false;
        }
    }
    if(isleft)
    {
        buff.append("L");
        left_pos = num;
    }
    else
    {
        buff.append("R");
        right_pos = num;
    }
}
    
String answer = buff.toString();

논리적으로 어려운 부분은 없다. 1,4,7인경우에는 왼손으로 누르므로 isleft를 true값으로 변경한다. 3,6,9인 경우 false로 바꾼다. 만약 중간에 있는 키패드인 경우 moves 값을 비교하여 판별한다. 만약 값이 같은 경우 어느 손잡이인지 보면 된다. 키패드를 누를 때마다 현재 있어야 하는 위치값을 업데이트 하는 것을 잊지 말자. numbers의 길이를 n이라고 하면 이 알고리즘의 시간복잡도는 \(O(n)\)이다.

테스트



옛날에 멋모르고 인턴에 지원했다가 이 문제만 2-3시간 풀고 포기한 경험이 있다. 그래서 그 때의 안 좋은 감정이 차올랐는데, 이번에는 30분정도 걸렸다. 내가 성장하고 있는 걸 느껴서 기쁘다. 첨언을 하자면 키패드를 자세히 보면 3으로 나머지연산과 나누기 연산을 하면 키패드의 어느 위치에 있는지 쉽게 알 수 있다. 이걸 활용하면 코드를 더 간결하게 만들 수 있을거라 생각한다.