프로그래머스 | Python | Hash, Greedy | 대충 만든 자판 (Lv.1)

코드

def solution(keymap, targets):
    # 키맵에서 각 문자 최소 누르기 횟수를 저장
    char_to_min_press = {}
    for key in keymap:
        for idx, char in enumerate(key):
            if char in char_to_min_press:
                char_to_min_press[char] = min(char_to_min_press[char], idx + 1)
            else:
                char_to_min_press[char] = idx + 1

    # 결과를 저장할 리스트
    result = []

    for target in targets:
        total_presses = 0
        for char in target:
            if char in char_to_min_press:
                total_presses += char_to_min_press[char]
            else:
                # 문자를 작성할 수 없는 경우
                total_presses = -1
                break
        result.append(total_presses)

    return result

---

코드 해설

1. 최소 누르기 횟수 사전 생성

char_to_min_press = {}
for key in keymap:
    for idx, char in enumerate(key):
        if char in char_to_min_press:
            char_to_min_press[char] = min(char_to_min_press[char], idx + 1)
        else:
            char_to_min_press[char] = idx + 1

• 각 문자에 대해 키맵에서 가장 적게 눌러야 하는 횟수를 저장합니다.
• 키맵에서 idx는 0부터 시작하므로, 실제 키를 누르는 횟수는 idx + 1입니다.
• 동일한 문자가 여러 키에 할당된 경우, 최소 누르기 횟수를 유지합니다.

2. 대상 문자열 변환

for target in targets:
    total_presses = 0
    for char in target:
        if char in char_to_min_press:
            total_presses += char_to_min_press[char]
        else:
            total_presses = -1
            break
    result.append(total_presses)

• 각 target 문자열의 문자를 확인하며, 최소 누르기 횟수를 합산합니다.
• 만약 키맵에 없는 문자가 있다면 작성 불가능하므로 -1을 저장하고 중단합니다.

3. 결과 반환

return result

• 각 문자열의 최소 누르기 횟수를 결과 리스트에 저장하고 반환합니다.

---

입출력 예제

예제: keymap = ["ABACD", "BCEFD"], targets = ["ABCD", "AABB"]

이 예제에서 목표는 targets에 있는 각 문자열을 작성하기 위해 최소 누르기 횟수를 계산하는 것입니다.

---

1. keymap 처리: 최소 누르기 횟수 계산

keymap의 각 문자를 순회하며, 해당 문자를 입력하기 위해 필요한 최소 횟수를 기록합니다.

첫 번째 키맵: "ABACD"

• 'A': 1번 누르면 입력 가능 → {'A': 1}
• 'B': 2번 누르면 입력 가능 → {'A': 1, 'B': 2}
• 'A': 이미 존재, 최소값 유지 → {'A': 1, 'B': 2}
• 'C': 4번 누르면 입력 가능 → {'A': 1, 'B': 2, 'C': 4}
• 'D': 5번 누르면 입력 가능 → {'A': 1, 'B': 2, 'C': 4, 'D': 5}

두 번째 키맵: "BCEFD"

• 'B': 첫 번째 위치 → 최소값 갱신: min(2, 1) → {'A': 1, 'B': 1, 'C': 4, 'D': 5}
• 'C': 두 번째 위치 → 최소값 갱신: min(4, 2) → {'A': 1, 'B': 1, 'C': 2, 'D': 5}
• 'E': 세 번째 위치 → 새로 추가: {'A': 1, 'B': 1, 'C': 2, 'D': 5, 'E': 3}
• 'F': 네 번째 위치 → 새로 추가: {'A': 1, 'B': 1, 'C': 2, 'D': 5, 'E': 3, 'F': 4}
• 'D': 다섯 번째 위치 → 최소값 유지: {'A': 1, 'B': 1, 'C': 2, 'D': 5, 'E': 3, 'F': 4}

최종 char_to_min_press 결과:

{'A': 1, 'B': 1, 'C': 2, 'D': 5, 'E': 3, 'F': 4}

---

2. targets 처리: 최소 누르기 횟수 계산

첫 번째 문자열: "ABCD"

1. 'A': 1번 누름.
2. 'B': 1번 누름.
3. 'C': 2번 누름.
4. 'D': 5번 누름.

총합: 1 + 1 + 2 + 5 = 9

두 번째 문자열: "AABB"

1. 'A': 1번 누름.
2. 'A': 1번 누름.
3. 'B': 1번 누름.
4. 'B': 1번 누름.

총합: 1 + 1 + 1 + 1 = 4

---

최종 결과

result = [9, 4]

---

코드의 흐름 설명

1. keymap을 순회하며 최소 누르기 횟수 계산:
   • 각 키맵의 문자와 위치를 기록.
   • 중복 문자가 등장하면, 기존 최소값과 비교해 더 작은 값을 저장.
2. targets의 각 문자 처리:
   • char_to_min_press에서 해당 문자의 값을 가져와 누르기 횟수를 더함.
   • 만약 char_to_min_press에 없는 문자가 있다면, 해당 문자열은 작성 불가 → 1 저장.

---

핵심 포인트

1. 효율적인 문자 검색: 딕셔너리(char_to_min_press)를 사용해 O(1)의 복잡도로 최소 누르기 횟수를 가져옴.
2. 문자열 탐색: targets를 순회하면서 각 문자의 누르기 횟수를 더함.
3. 예외 처리: 작성 불가한 문자열은 1을 반환.
4. 시간 복잡도:

•  키맵 크기: O(n * m) (n: 키맵 길이, m: 각 키의 길이).
•   대상 문자열 크기: O(t * l) (t: 타겟 문자열 수, l: 타겟 문자열 길이).
•   총 시간 복잡도: O(n * m + t * l).

---

관련 문법

1. enumerate:
   •   리스트를 순회하며 인덱스와 값을 동시에 가져옴.
   •   사용 예: for idx, char in enumerate(key):
2. dict 활용:
   •  키를 사용해 문자 최소 누르기 횟수를 빠르게 조회.

---

✅ 알고리즘 유형

1. 해시맵(Hash Map, 딕셔너리) 활용
   •   char_to_min_press 딕셔너리를 사용하여 각 문자에 대한 최소 키 입력 횟수를 저장합니다.
   •   이를 통해 문자 입력 시 빠르게 최적의 키 입력 횟수를 찾을 수 있음 (O(1) 조회 속도).
2. 그리디(Greedy) 알고리즘
   •   각 target 문자열을 구성하는 데 필요한 최소 키 입력 횟수를 탐색할 때,
     항상 최소한의 입력 횟수를 선택하여 더합니다.
   •   즉, 현재 상황에서 가장 적은 키 입력을 하는 방법을 선택하는 전략입니다.