[Programmers] 키패드 누르기

문제

문제 바로가기

나의 코드

---

# 키패드 누르기

from collections import deque

# 키패드 번호간의 거리를 구해 리턴하는 함수 - BFS
def get_distance(start, end):
    visited = [[0 for _ in range(3)] for _ in range(4)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    q = deque()
    q.append(start)
    visited[start[0]][start[1]] = 1 # 시작위치 방문처리
    
    while q:
        x, y = q.popleft()
        
        # (x,y)가 end인 경우
        if x == end[0] and y == end[1]:
            return visited[x][y] - 1
        
        for i in range(4):
            tx = x + dx[i]
            ty = y + dy[i]
            
            # 이동했을 때의 위치가 키패드 범위 내에 있고 방문하지 않은 경우
            if (0<= tx <=2 and 0<=ty<=2) or (tx==3 and ty==1):
                if visited[tx][ty] == 0:
                    q.append((tx,ty))
                    visited[tx][ty] = visited[x][y] + 1
                    
    return 0
            
        
    
    
def solution(numbers, hand):
    answer = ''
    # 각 기패드 번호의 좌표를 담은 딕셔너리
    keypads = {1:(0,0), 2:(0,1), 3:(0,2), 4:(1,0), 5:(1,1), 6:(1,2), 7:(2,0), 8:(2,1), 9:(2,2), 0:(3,1)}
    
    # 현재 오른손과 왼손의 위치 - 시작 위치로 초기화
    right_hand = (3,2)
    left_hand = (3,0)
    
    # 누른 번호 순서대로 탐색
    for num in numbers:

        #현재 누른 번호의 좌표(위치)
        num_loc = keypads[num]
        
        # 1,4,7 누른 경우 -> 왼손
        if num_loc[1] == 0:
            answer += "L"
            left_hand = num_loc
        # 3,6,9 누른 경우 -> 오른손
        elif num_loc[1] == 2:
            answer += "R"
            right_hand = num_loc
        #가운데 2,5,8,0 누른 경우
        else:
            rdist = get_distance(right_hand, num_loc) #오른손으로 누를 경우 거리
            ldist = get_distance(left_hand, num_loc) #왼손으로 누를 경우 겨리
            
            # 왼손이 더 가까이 있음
            if rdist > ldist:
                answer += "L"
                left_hand = num_loc
            # 오른손이 더 가까이 있음
            elif rdist < ldist:
                answer += "R"
                right_hand = num_loc
            # 왼손과 오른손의 거리가 같음
            else:
                # 오른손잡이인 경우
                if hand == "right":
                    answer += "R"
                    right_hand = num_loc
                # 왼손잡이인 경우
                elif hand == "left":
                    answer += "L"
                    left_hand = num_loc
    return answer

코드 풀이

• 키패드 번호의 좌표를 딕셔너리로 담았다.
• 키패드 1, 4, 7을 누른 경우 🟰 (x,y) y좌표가 0인 경우
• 키패드 3, 6, 9을 누른 경우 🟰 (x,y) y좌표가 2인 경우
• 키패드 2, 5, 8, 0을 누른 경우 🟰 (x,y) y좌표가 1인 경우
  • '오른손을 사용했을 때'와 '왼손을 사용했을 때'의 키패드간의 거리를 계산한 뒤 비교한다.
  • 거리가 같으면 오른손잡이인지 왼손잡이인지에 따라 결정

키패드 간의 거리를 계산하는 법
나는 BFS를 사용해 키패드 간의 거리를 계산했지만 아래의 '다른코드1'의 절댓값으로 거리를 계산하는 방법이 훨씬 더 효율적이다.

다른 코드1

---

# 키패드 누르기_2

def solution(numbers, hand):
    answer = ''
    # 각 기패드 번호의 좌표를 담은 딕셔너리
    key_dict = {1:(0,0),2:(0,1),3:(0,2),
                4:(1,0),5:(1,1),6:(1,2),
                7:(2,0),8:(2,1),9:(2,2),
                '*':(3,0), 0:(3,1),'#':(3,2)}

    left = [1,4,7] #왼손을 사용해야하는 번호
    right = [3,6,9] #오른손을 사용해야하는 번호

    #오른손과 왼손 시작위치 초기화
    left_hand = '*'
    right_hand = '#'

    # 누른 번호 순서대로 탐색
    for num in numbers:
        # 1,4,7 누른 경우 -> 왼손
        if num in left:
            answer += 'L'
            left_hand = num
        # 3,6,9 누른 경우 -> 오른손
        elif num in right:
            answer += 'R'
            right_hand = num
        #가운데 2,5,8,0 누른 경우
        else:
            curPos = key_dict[num] #현재 누른 번호의 좌표
            lPos = key_dict[left_hand] #현재 왼손의 위치
            rPos = key_dict[right_hand] #현재 오른손의 위치

            ldist = abs(curPos[0]-lPos[0]) + abs(curPos[1]-lPos[1]) #오른손으로 누를 경우 거리
            rdist = abs(curPos[0]-rPos[0]) + abs(curPos[1]-rPos[1]) #왼손으로 누를 경우 거리

            # 왼손이 더 가까이 있음
            if ldist < rdist:
                answer += 'L'
                left_hand = num
            # 오른손이 더 가까이 있음
            elif ldist > rdist:
                answer += 'R'
                right_hand = num
            # 왼손과 오른손의 거리가 같음
            else:
                # 왼손잡이인 경우
                if hand == 'left':
                    answer += 'L'
                    left_hand = num
                # 오른손잡이인 경우
                else:
                    answer += 'R'
                    right_hand = num

    return answer

코드 풀이

나의 코드와 전체적인 알고리즘은 비슷하다. 나의 코드에서는 '키패드의 좌표'를 중점으로 왼손인지 오른손인지를 판단하였고, 다른 코드1에서는 '키패드 번호 자체'를 중점으로 판단한다.
'키패드 번호 자체'로 오른손인지 왼손인지 판단하는 것이 가독성 면에서는 더 좋은것 같다.

키패드 간의 거리를 계산하는 법
(a,b) 와 (c,d) 간의 거리를 계산한다 가정했을 때, 다음과 같이 행 간의 거리 + 열 간의 거리로 계산한다.

distance = abs(a-c) + abs(b-d)

나의코드에서는 BFS로 거리를 구했는데 절댓값으로 거리를 구하는 것이 훨~씬 더 효율적이고 코드도 짧다.

다른 코드2

---

# 키패드 누르기_3

def solution(numbers, hand):
    answer = ""

    #왼손과 오른손의 시작위치 초기화
    left_hand = 10 #10은 *을 뜻함
    right_hand = 11 #11은 #을 뜻함

    #distance[x][y] = 키패드x번과 키패드y번 사이의 거리
    distance = [[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 num in numbers:
        if num in [1, 4, 7]:
            left_hand = num
            answer += "L"
        elif num in [3, 6, 9]:
            right_hand = num
            answer += "R"
        else:
            # 왼손이 더 가까이 있음
            if distance[left_hand][num] < distance[right_hand][num]:
                left_hand = num
                answer += "L"
            # 오른손이 더 가까이 있음
            elif distance[left_hand][num] > distance[right_hand][num]:
                right_hand = num
                answer += "R"
            # 왼손과 오른손의 거리가 같고 왼손잡이인 경우
            elif hand == "left":
                left_hand = num
                answer += "L"
            # 왼손과 오른손의 거리가 같고 오른손잡이인 경우
            else:
                right_hand = num
                answer += "R"
    return answer

코드 풀이

→ 좌표를 저장하는 것이 아니라 아예 거리를 저장하는 방식.
키패드x번과 키패드y번 사이의 거리를 미리 2차원 배열에 저장해두고 비교한다.
속도면에서는 다른 코드2방식이 가장 빠를것 같다.

Comment

키패드 간의 거리 계산할 때 왜 x좌표간의 거리와 y좌표간의 거리를 더하는 방식은 생각하지 못했을까... 2차원배열에서 최단거리 구하는것은 BFS라고만 생각했다...ㅜ 다른코드2의 방식은 키패드간의 거리계산이 귀찮을수는 있어도 가장 빠른 방법인것 같다.