[프로그래머스] [python] 대충 만든 자판

처음 시도한 코드

def solution(keymap, targets):
    l = len(keymap)
    answer = []
    for i in range(l):
        count = 0
        for t in targets[i]:
            n = -1
            for k in keymap:
                if t in k:
                    temp = k.index(t) + 1
                    if n==-1:
                        n = temp
                    elif n>0 and n > temp:
                        n = temp
                        break
            count += n
            if n==-1:
                break
        answer.append(count)
    return answer

입출력 예를 살펴보면, targets의 B가 keymap의 첫번째 키, 두번째 키에도 있으므로 각 타겟에 대해 모든 keymap을 살펴봐야 한다고 생각하여 각 key에서 B의 최소 카운트 수를 구하여 비교하는 식으로 코드를 작성하였다.

테스트 코드는 통과하였지만, 실행 실패가 되어 내 코드의 문제점을 지피티와 함께 분석해 보았다.

문제점

1. targets의 길이와 무관하게 keymap을 기준으로 반복문 설계

2. 내부에서 각 문자를 찾기 위해 for k in keymap 사용

- 시간 복잡도 증가 -> 이를 개선하기 위해 각 문자가 나타나는 최소 키 입력 횟수를 미리 계산해놓는 것이 이 문제의 핵심이었다.

3. 조건 누락

n = -1일때의 처리가 확실하게 되지 않고 있다.

개선 코드

def solution(keymap, targets):
    # 최소 입력 횟수를 저장할 딕셔너리 생성
    min_presses = {}
    
    # keymap을 순회하며 각 문자의 최소 입력 횟수를 기록
    for i, keys in enumerate(keymap):
        for j, char in enumerate(keys):
            if char in min_presses:
                min_presses[char] = min(min_presses[char], j + 1)
            else:
                min_presses[char] = j + 1
    
    # 결과를 저장할 리스트
    answer = []
    
    # 각 target 문자열에 대해 계산
    for target in targets:
        press_count = 0
        for char in target:
            if char in min_presses:
                press_count += min_presses[char]
            else:
                # 목표 문자열을 작성할 수 없는 경우
                press_count = -1
                break
        answer.append(press_count)
    
    return answer