프로그래머스, 키패드 누르기

프로그래머스, 키패드 누르기

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

프로그래머스

 

분류

pass

요새 BFS문제를 많이 푸는 중이다.

 

2023.08.09 - [알고리즘] - 백준, 이모티콘

저번에 풀었던 최단시간 문제 이모티콘도 그렇고!

이번에는 최단거리 문제!

 

예전에 이문제를 이차원배열로 푼적이 있다.

2023.01.22 - [알고리즘] - 데일리 알고리즘 230120

데일리 알고리즘 230120

무려 5시간이 걸려서..

이번에는 BFS로 30분안에 풀었다!!!(매우 뿌듯)

 

풀이

딕셔너리를 활용해 각 버튼을 노드로 생각하고 1칸으로 이동할 수 있는 노드를 다 추가해줬다.

keypad = {
    1: [2,4],
    2: [1,3,5],
    3: [2,6],
    4: [1,5,7],
    5: [2,4,6,8],
    6: [3,5,9],
    7: [4,8,'*'],
    8: [5,7,9,0],
    9: [6,8,'#'],
    '*' : [7,0],
    0: ['*', '#', 8],
    '#' : [9,0]
}

 

그런 다음에 시작 노드에서 다음 노드까지 가는 최단 거리를 반환하는 함수를 짰다.

def distance(start, end):
    queue = deque([(start, 0)])
    visited = set()

    while queue:
        node, dist = queue.popleft()
        visited.add(node)

        if node == end:
            return dist
        for neighbor in keypad[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))

    return -1

모든 노드가 이어져 있는 형태라 도달하지 못할 케이스는 없지만, 그래도 도달하지 못할 경우 -1을 반환하도록 코드를 짰다.

 

다음부터는 문제를 푸는 로직이다.

num가 1,4,7이면 무조건 왼손으로하고 현재 왼손의 위치 업데이트!

num가 3,6,9이면 무조건 오른손으로하고 현재 오른손 위치 업테이트!

num이 2,5,8,0이면 현재 왼손에서 num까지의 거리와 현재 오른손에서 num까지 도달하는 거리 비교해 더짧은쪽으로 손을 움직인다. 만약 같을 경우, 사용자가 왼손잡이인지 오른손잡이인지에 따라 이동하는 손이 달라진다.

 

나의 코드

from collections import deque

keypad = {
    1: [2,4],
    2: [1,3,5],
    3: [2,6],
    4: [1,5,7],
    5: [2,4,6,8],
    6: [3,5,9],
    7: [4,8,'*'],
    8: [5,7,9,0],
    9: [6,8,'#'],
    '*' : [7,0],
    0: ['*', '#', 8],
    '#' : [9,0]
}

def distance(start, end):
    queue = deque([(start, 0)])
    visited = set()

    while queue:
        node, dist = queue.popleft()
        visited.add(node)

        if node == end:
            return dist
        for neighbor in keypad[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))

    return -1

numbers = [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2]
hand = "left"

right = '#'
left = '*'

result = ''
for num in numbers:
    if num in [1,4,7]:
        result += 'L'
        left = num
    elif num in [3,6,9]:
        result += 'R'
        right = num
    else:
        if distance(left, num) < distance(right, num):
            result += 'L'
            left = num
        elif distance(left, num) > distance(right, num):
            result += 'R'
            right = num
        else:
            if hand == "right":
                result += 'R'
                right = num
            elif hand == "left":
                result += 'L'
                left = num

print(result)

 

제출용 코드

from collections import deque

keypad = {
    1: [2,4],
    2: [1,3,5],
    3: [2,6],
    4: [1,5,7],
    5: [2,4,6,8],
    6: [3,5,9],
    7: [4,8,'*'],
    8: [5,7,9,0],
    9: [6,8,'#'],
    '*' : [7,0],
    0: ['*', '#', 8],
    '#' : [9,0]
}

def distance(start, end):
    queue = deque([(start, 0)])
    visited = set()

    while queue:
        node, dist = queue.popleft()
        visited.add(node)

        if node == end:
            return dist
        for neighbor in keypad[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))

    return -1

def solution(numbers, hand):
    right = '#'
    left = '*'

    result = ''
    for num in numbers:
        if num in [1,4,7]:
            result += 'L'
            left = num
        elif num in [3,6,9]:
            result += 'R'
            right = num
        else:
            if distance(left, num) < distance(right, num):
                result += 'L'
                left = num
            elif distance(left, num) > distance(right, num):
                result += 'R'
                right = num
            else:
                if hand == "right":
                    result += 'R'
                    right = num
                elif hand == "left":
                    result += 'L'
                    left = num

    return result

---

bfs 사용하지 않고 이차원 좌표값을 딕셔너리를 활용해 풀 수 있다.

코드는 아래와 같다.

 

📜이차원 배열 풀이

def move(curPad, nextPad):
    x1, y1 = curPad
    x2, y2 = nextPad
    return abs(x1-x2)+abs(y1-y2)

def solution(numbers, hand):
    keypad = {
        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, right = keypad['*'], keypad['#']
    
    answer = ''
    for number in numbers:
        nextPad = keypad[number]
        leftMove = move(left, nextPad)
        rightMove = move(right, nextPad)
        if number in [1,4,7] or (number in [2,5,8,0] and leftMove < rightMove):
            left = nextPad
            answer+='L'
        elif number in [3,6,9] or (number in [2,5,8,0] and leftMove > rightMove):
            right = nextPad
            answer+='R'
        else:
            if hand == 'left':
                answer+='L'
                left = nextPad
            else:
                answer+='R'
                right = nextPad
                    
    return answer