[Programmers] 2020 카카오 인턴십 - 키패드 누르기 (Swift)

문제 :

https://programmers.co.kr/learn/courses/30/lessons/67256

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

 

Step 1. 문제 이해하기

• 왼손, 오른손 엄지는 각각 '*', '#'에 위치해 있고 왼쪽 키패드(1, 4, 7)는 무조건 왼손이 클릭하고 오른쪽 키패드(3, 6, 9)는 오른손이 클릭
• 중앙 키패드(2, 5, 8, 0)를 클릭할 때는 왼손 또는 오른손 중 가까운 손으로 클릭하고, 왼손 오른손 각각의 위치에서 중앙 키패드로  가는 거리가 서로 같으면 hand에 저장된 방향으로 클릭

 

Step 2. 문제 풀이 생각하기

1. 처음 생각한 것은 각각의 키패드 번호와 키패드 좌표를 해시 테이블 형태로 만들어야겠다고 생각했습니다.
2. 그리고 중앙 키패드를 누를 때 중앙 키패드까지의 왼손과 오른손의 거리를 BFS로 구해야겠다고 생각해서 구현했는데, 테스트 1에서 시간 초과가 발생했습니다.
3. 그래서 식으로 바로 거리를 구할 수 있는 방법이 없을까 생각하다가 1차원에서의 2점 사이의 거리 공식이 생각났습니다.

파란 점에서 빨간 점으로 가는 최단 거리를 구한다고 했을 때,

파란 점에서 초록점을 거쳐 빨간점에 도달하는 것을 식으로 표현하면

distance = |X2 - X1| + |Y2 - Y1|

이 되는 것을 알 수 있습니다.

 

Step 3. 차근차근 구현하기

import Foundation

func solution(_ numbers:[Int], _ hand:String) -> String {
    var ans = ""
    let l = [1 : (0, 0), 4 : (1, 0), 7 : (2, 0)] // 왼쪽 키패드 좌표
    let m = [2 : (0, 1), 5 : (1, 1), 8 : (2, 1), 0 : (3, 1)] // 중앙 키패드 좌표
    let r = [3 : (0, 2), 6 : (1, 2), 9 : (2, 2)] // 오른쪽 키패드 좌표
    var lf = (3, 0) // 왼손 엄지 손가락 위치
    var rf = (3, 2) // 오른손 엄지 손가락 위치
    
    for number in numbers {
        // 왼쪽 키패드일 떄
        if let matrix = l[number] {
            ans += "L"
            lf = matrix // 왼손 좌표 옮기기
        }
        // 오른쪽 키패드일 떄
        else if let matrix = r[number] {
            ans += "R"
            rf = matrix // 오른손 좌표 옮기기
        }
        // 중앙 키패드일 떄
        else {
            let matrix = m[number]!
            let l_dist = abs((matrix.0 - lf.0)) + abs(matrix.1 - lf.1)
            let r_dist = abs((matrix.0 - rf.0)) + abs(matrix.1 - rf.1)
            
            // 중앙 패드에서 왼손이 더 가까울 때
            if l_dist < r_dist {
                ans += "L"
                lf = matrix
            }
            
            // 중앙 패드에서 오른손이 더 가까울 때
            else if l_dist > r_dist {
                ans += "R"
                rf = matrix
            }
            
            // 중앙 패드에서 왼손, 오른손 거리가 같을 경우
            else {
                if hand == "left" {
                    ans += "L"
                    lf = matrix
                }
                else {
                    ans += "R"
                    rf = matrix
                }
            }
        }
    }
    return ans
}

 

Step 4. 피드백

• 기하학같은 수학적 사고력을 요구하는 문제들도 나오는 만큼 좀 더 다양한 문제를 풀어봐야겠다고 생각했습니다.