[Level 1] 키패드 누르기

 문제 

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

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

 사용 언어 

Python3

 풀이 과정 

문제를 천천히 이해하며 풀었는데 로직은 다 맞는 것 같았는데 이상하게 띄엄 띄엄 6문제만 오답이었다.

차라리 틀릴거면 다 틀려야하는데 너어무 답답해서 테스트 케이스를 추가하고 내 머리의 정답과 비교했는데

운이 좋게 바로 틀린 테스트 케이스를 찾을 수 있었다.

그런데 아무리 봐도 로직에는 문제가 없어보여서 살짝 걸렸던 좌표 설정을 바꿔봤더니 해결됐다...

나는 0번을 (0, 0) 원점으로 삼은 좌표값을 사용했는데 정확한 이유는 모르겠지만 그러면 거리를 구할 때 -로만 했어야 하는데 절댓값까지 사용해서..? 거리가 좀 이상하게 찍히는 경우가 있었나보다.

numInfo = {1: (-1, 3), 2: (0, 3), 3: (1, 3), 4: (-1, 2), 5: (0, 2),
	6: (1, 2), 7: (-1, 1), 8: (0, 1), 9:(1, 1), 0: (0, 0)}

그래서 다시 *을 (0, 0)으로 설정한 좌표값으로 모두 바꿔주었더니(제출 답안) 깔끔하게 통과되었다!

 제출 답안 

# 왼손 : 1, 4, 7 -> 3으로 나눴을 때 나머지 1
# 오른손 : 3, 6, 9 -> 3의 배수
# 나머지 : 마지막 위치에서 더 가까운 손
# 현재 왼손, 오른손 위치는 *이 원점인 좌표로 표기

def solution(numbers, hand):
    numInfo = {1: (0, 3), 2: (1, 3), 3: (2, 3), 4: (0, 2), 5: (1, 2), 6: (2, 2), 7: (0, 1), 8: (1, 1), 9:(2, 1), 0: (1, 0)}
    
    result = ["L"] * len(numbers)
    left = (0, 0)
    right = (2, 0)
    for i, num in enumerate(numbers):
        if num % 3 == 0 and num != 0: # right
            right = numInfo[num]
            result[i] = "R"
        elif num % 3 == 1: # left
            left = numInfo[num]
        else: # 나머지
            tx, ty = numInfo[num]
            rx, ry = right
            lx, ly = left
            distanceR = abs(tx-rx) + abs(ty-ry)
            distanceL = abs(tx-lx) + abs(ty-ly)
            if distanceR < distanceL:
                right = numInfo[num]
                result[i] = "R"
            elif distanceR > distanceL:
                left = numInfo[num]
            else:
                if (hand == "right"):
                    right = numInfo[num]
                    result[i] = "R"
                else:
                    left = numInfo[num]
    
    return "".join(result)

 공부한 내용 

맨하튼 거리

미국 뉴욕시 행정 구역인 그 맨하탄이 맞다. 맨하탄은 인류 최초의 현대 대도시로 불리며, 맨하탄의 상징적인 이미지는 빌딩숲의 이미지에서 따왔다고 한다.

 

아래의 그림에서 빨간선, 파란선, 노란선은 모두 같은 거리로 맨하탄 거리라고 부를 수 있는 것이다.

초록선은 또다른 기초적인 좌표간의 거리를 구할 수 있는 유클리드 거리이다.

맨하탄 거리는 왼쪽 아래의 좌표를 (x1, y1)이라 하고 우측 상단의 좌표를 (x2, y2)라고 할 때, 맨하탄 좌표의 공식을 적어보면 다음과 같다.

 

|x1 - x2| + |y1 - y2|

 

결국 x값의 차와 y값의 차를 각각 절대값으로 바꾼 후, 합한 값이 바로 맨하탄 거리 공식이다. 이 알고리즘을 3차원으로 확장하면 다음과 같다.

 

|x1 - x2| + |y1 - y2| + |z1 - z2|

근데 맨하탄 거리라는 이름을 알지 못했어도 중등~고등 수학과정에서 이 공식을 많이 사용했었던 것 같다.

진짜 다 까먹었지만 내가 본능적으로 피타고라스 공식이 아닌 저 공식을 사용한 거 보면...

 

출처: https://needjarvis.tistory.com/455

유클리드 거리

공부한김에 가장 널리 쓰이는 거리 계산 방법인 유클리드 거리도 정리하고 넘어가자.

피타고라스 정리를 사용한 거리를 측정하는 방법이 맞다. 공식은 다음과 같다.

 

맨하튼 거리보다는 조금 더 복잡해서 파이썬으로 구현하는 방법을 알아보자. numpy 모듈의 메소드들을 사용해서 간단하게 구할 수 있다.

import numpy as np
a = np.array((1, 2, 3))
b = np.array((4, 5, 6))

dist = np.sqrt(np.sum(np.square(a-b)))

print(dist)

또 math.dist( ) 함수를 사용하면 훨씬 편하게 구현할 수 있었다.

from math import dist

a = (1, 2, 3)
b = (4, 5, 6)

print(dist(a,b))

 

출처: https://www.delftstack.com/ko/howto/numpy/calculate-euclidean-distance/

 다른 사람 답안 

역시나 다른 사람 답안이 궁금해서 봤는데, in [1, 4, 7] 이런식으로 표현한 사람이 많았는데

효율면에서는 나처럼 계산이 조금 더 빠를 것 같았다.

그리고 아래 답안은 신박해서 데려온건데 나도 초반에 잠깐 스쳐지나간 생각이었지만 그렇게 푸는 문제가 아닌 것 같아 다시 생각했지만 ㅋㅋㅋㅋㅋㅋ 귀찮음을 감수하면 속도면에서는 빠르기 때문에!

어쨌든 모든 버튼에서의 다른 버튼까지 거리를 직접 저장해놓고 비교해서 푸는 로직이다.

def solution(numbers, hand):
    l = 10
    r = 11
    answer = ""
    p = [[0, 4, 3, 4, 3, 2, 3, 2, 1, 2],
         [4, 0, 1, 2, 0, 2, 3, 0, 3, 4],
         [3, 1, 0, 1, 2, 1, 2, 3, 2, 3],
         [4, 2, 1, 0, 3, 2, 1, 4, 3, 2],
         [3, 0, 2, 3, 0, 1, 2, 0, 2, 3],
         [2, 2, 1, 2, 1, 0, 1, 2, 1, 2],
         [3, 3, 2, 1, 2, 1, 0, 3, 2, 1],
         [2, 0, 3, 4, 0, 2, 3, 0, 1, 2],
         [1, 3, 2, 3, 2, 1, 2, 1, 0, 1],
         [2, 4, 3, 2, 3, 2, 1, 2, 1, 0],
         [1, 0, 4, 5, 0, 3, 4, 0, 2, 3],
         [1, 5, 4, 0, 4, 3, 0, 3, 2, 0]]
    for i in numbers:
        if i in [1, 4, 7]:
            l = i
            answer += "L"
        elif i in [3, 6, 9]:
            r = i
            answer += "R"
        else:
            if p[l][i] < p[r][i]:
                l = i
                answer += "L"
            elif p[l][i] > p[r][i]:
                r = i
                answer += "R"
            elif hand == "left":
                l = i
                answer += "L"
            else:
                r = i
                answer += "R"
    return answer

출처: 프로그래머스 다른 사람의 풀이