문제
https://programmers.co.kr/learn/courses/30/lessons/67256
코딩테스트 연습 - 키패드 누르기
[1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL"
programmers.co.kr
사용 언어
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
출처: 프로그래머스 다른 사람의 풀이
'코딩 테스트 스터디 > 프로그래머스' 카테고리의 다른 글
[level 2] 오픈채팅방 (0) | 2022.07.21 |
---|---|
[level 1] 신고 결과 받기 (0) | 2022.07.20 |
[Level 2] 정렬. 가장 큰 수 (0) | 2022.03.01 |
[Level 2] 스택/큐. 다리를 지나는 트럭 (0) | 2022.02.25 |
[Level 2] 스택/큐. 프린터 (0) | 2022.02.24 |