99클럽 코테 스터디 5일차 TIL

[level 3] 숫자 타자 대회 - 136797

문제 링크

성능 요약

메모리: 285 MB, 시간: 2222.80 ms

구분

코딩테스트 연습 > 연습문제

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2024년 04월 17일 23:31:06

문제 설명

위와 같은 모양으로 배열된 숫자 자판이 있습니다. 숫자 타자 대회는 이 동일한 자판을 사용하여 숫자로만 이루어진 긴 문자열을 누가 가장 빠르게 타이핑하는지 겨루는 대회입니다.

대회에 참가하려는 민희는 두 엄지 손가락을 이용하여 타이핑을 합니다. 민희는 항상 왼손 엄지를 4 위에, 오른손 엄지를 6 위에 두고 타이핑을 시작합니다. 엄지 손가락을 움직여 다음 숫자를 누르는 데에는 일정 시간이 듭니다. 민희는 어떤 두 숫자를 연속으로 입력하는 시간 비용을 몇몇 가중치로 분류하였습니다.

• 이동하지 않고 제자리에서 다시 누르는 것은 가중치가 1입니다.
• 상하좌우로 인접한 숫자로 이동하여 누르는 것은 가중치가 2입니다.
• 대각선으로 인접한 숫자로 이동하여 누르는 것은 가중치가 3입니다.
• 같지 않고 인접하지 않은 숫자를 누를 때는 위 규칙에 따라 가중치 합이 최소가 되는 경로를 따릅니다.

예를 들어 1 위에 있던 손가락을 0 으로 이동하여 누르는 것은 2 + 2 + 3 = 7 만큼의 가중치를 갖습니다.
단, 숫자 자판은 버튼의 크기가 작기 때문에 같은 숫자 버튼 위에 동시에 두 엄지 손가락을 올려놓을 수 없습니다. 즉, 어떤 숫자를 눌러야 할 차례에 그 숫자 위에 올려져 있는 손가락이 있다면 반드시 그 손가락으로 눌러야 합니다.

숫자로 이루어진 문자열 numbers가 주어졌을 때 최소한의 시간으로 타이핑을 하는 경우의 가중치 합을 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ numbers의 길이 ≤ 100,000
  • numbers는 아라비아 숫자로만 이루어진 문자열입니다.

---

입출력 예

numbers	result
"1756"	10
"5123"	8

---

입출력 예 설명

입출력 예 #1
왼손 엄지로 17, 오른손 엄지로 56을 누르면 가중치 10으로 최소입니다.

입출력 예 #2
오른손 엄지로 5, 왼손 엄지로 123을 누르거나 오른손 엄지로 5, 왼손 엄지로 1, 오른손 엄지로 23을 누르면 가중치 8로 최소입니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

코딩테스트 연습 | 프로그래머스 스쿨

 

풀이 - BFS

import sys
sys.setrecursionlimit(10**6)
from collections import deque
def bfs(si, sj, num, w, move, board, diagonal) :
    q = deque()
    q.append((si, sj, num, 0))
    w[num][num] = 1

    while q :
        curr = q.popleft()

        for d in range(4) : # 상하좌우 이동
            ni = curr[0] + move[d][0]
            nj = curr[1] + move[d][1]

            if check(ni, nj) == 1 and board[ni][nj] != "*" and board[ni][nj] != "#" \
                and w[num][int(board[ni][nj])] > curr[3] + 2 :
                w[num][int(board[ni][nj])] = curr[3] + 2
                w[int(board[ni][nj])][num] = curr[3] + 2
                q.append((ni, nj , int(board[ni][nj]), curr[3] + 2))

        for d in range(4) : # 대각 이동
            ni = curr[0] + diagonal[d][0]
            nj = curr[1] + diagonal[d][1]

            if check(ni, nj) == 1 and board[ni][nj] != "*" and board[ni][nj] != "#" \
                    and w[num][int(board[ni][nj])] > curr[3] + 3:
                w[num][int(board[ni][nj])] = curr[3] + 3
                w[int(board[ni][nj])][num] = curr[3] + 3
                q.append((ni, nj, int(board[ni][nj]), curr[3] + 3))

def check(r, c):
    if 0 <= r < 4 and 0 <= c < 3 :
        return True
    return False

def getMinTime(idx, left, right, n, dp, INF, number, w) :
    if idx == n :
        return 0

    if dp[idx][left][right] == INF :
        first = INF
        second = INF
        if right != number[idx] :
            first = w[left][number[idx]] + getMinTime(idx + 1, number[idx], right, n, dp, INF, number, w)
        if left != number[idx] :
            second = w[right][number[idx]] + getMinTime(idx + 1, number[idx], left, n, dp, INF, number, w)

        dp[idx][left][right] = min(first, second)

    return dp[idx][left][right]

def solution(numbers):
    INF = float('inf')
    n = len(numbers)
    number = [int(num) for num in numbers]
    dp = [[[INF] * 10 for _ in range(10)] for _ in range(n)]
    move = [(-1, 0), (1,0), (0,-1),(0,1)]
    diagonal = [(-1,-1), (1,-1), (-1,1), (1,1)]
    board = [['1','2','3'],
             ['4','5','6'],
             ['7','8','9'],
             ['*','0','#']]
    w = [[100] * 10 for _ in range(10)]
    for i in range(4) :
        for j in range(3) :
            if board[i][j] != '*' and board[i][j] != '#' :
                bfs(i, j, int(board[i][j]), w, move, board, diagonal)

    return getMinTime(0, 4, 6, n, dp, INF, number, w)

• 중간에 런타임 에러가 발생하여 로직이 이상한가 생각해서 sys.setrecursionlimit(10**6)으로 늘려주었더니 통과됨.
• BFS 를 기반으로 알고리즘을 구성하였음.
• 범위내, 조건 = 다음 좌표가 * 또는 # 이 아닐 경우, 를 dp 테이블에 저장
• dp는 float('inf')를 초기값으로 설정하여 최소값을 얻기 위한 알고리즘을 구성
• 다른 풀이를 보니 weight를 하나하나 다 구해서 array로 구성한 뒤 푸는 방법이 있었으나, 그 방법도 한 번 보는 것도 좋아보임.
• 구현 과정에서 어려운 과정이 많아 다른 분의 코드를 많이 참고하였음.