[본캠프] 데이터기반 QA/QC 부트캠프 38일차

1. 오늘의 학습 목표

오늘은 프로그래머스 문제 **「대충 만든 자판」**을 풀면서 딕셔너리를 활용한 문자열 처리 방법을 정리했다.

이번 문제는 휴대폰 자판처럼 하나의 키에 여러 문자가 할당되어 있을 때, 특정 문자열을 만들기 위해 각 문자를 최소 몇 번 눌러야 하는지 계산하는 문제였다.

처음 보면 단순히 문자열을 하나씩 비교하면 될 것 같지만, 같은 문자가 여러 키에 중복으로 들어갈 수 있기 때문에 각 문자별 최소 입력 횟수를 먼저 구해두는 것이 중요했다.

오늘의 핵심은 다음과 같다.

• 자판 배열 keymap을 순회하면서 문자별 최소 입력 횟수 저장하기
• 목표 문자열 targets를 하나씩 확인하면서 필요한 입력 횟수 합산하기
• 만들 수 없는 문자가 있으면 -1 반환하기
• 딕셔너리를 이용해 문자 탐색을 빠르게 처리하기

---

2. 오늘 학습한 내용

문제 이해

문제에서는 keymap과 targets가 주어진다.

keymap은 휴대폰 자판에 어떤 문자들이 어떤 순서로 배치되어 있는지를 나타내는 배열이다.

예를 들어 어떤 키가 "ABACD"라면, 해당 키를 한 번 누르면 A, 두 번 누르면 B, 세 번 누르면 다시 A, 네 번 누르면 C, 다섯 번 누르면 D가 입력된다.

여기서 중요한 점은 같은 문자가 여러 번 등장할 수 있다는 것이다.

예를 들어 A가 1번째에도 있고 3번째에도 있다면, 당연히 1번만 눌러서 입력하는 것이 더 좋다. 그래서 문자마다 가장 적은 입력 횟수만 저장해야 한다.

목표는 targets 안에 있는 각 문자열을 만들기 위해 최소 몇 번 키를 눌러야 하는지 구하는 것이다.

만약 어떤 목표 문자열 안에 자판 어디에도 없는 문자가 들어 있다면, 그 문자열은 만들 수 없으므로 -1을 반환해야 한다.

---

문제 접근

처음에는 각 target 문자열마다 keymap 전체를 계속 확인하는 방식도 생각할 수 있다.

하지만 그렇게 하면 같은 문자를 찾기 위해 매번 keymap을 반복해서 탐색해야 한다. 문제 제한이 아주 크지는 않지만, 굳이 비효율적으로 풀 필요는 없다.

그래서 먼저 keymap을 한 번 순회하면서 각 문자를 입력하기 위해 필요한 최소 횟수를 딕셔너리에 저장한다.

예를 들어 딕셔너리는 이런 형태가 된다.

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

이렇게 미리 정리해두면 target 문자열을 확인할 때는 각 문자가 딕셔너리에 있는지만 보면 된다.

문자를 만들 수 있으면 해당 횟수를 더하고, 만들 수 없는 문자가 나오면 바로 -1로 처리한다.

전체 흐름은 다음과 같다.

1. 빈 딕셔너리 key_count를 만든다.
2. keymap을 순회하면서 각 문자의 최소 입력 횟수를 저장한다.
3. targets를 하나씩 확인한다.
4. target 안의 각 문자가 딕셔너리에 있으면 입력 횟수를 더한다.
5. 딕셔너리에 없는 문자가 있으면 -1을 저장하고 반복을 멈춘다.
6. 각 target의 결과를 answer에 담아 반환한다.

---

풀이 코드

def solution(keymap, targets):
    answer = []
    key_count = {}

    for key in keymap:
        for idx, char in enumerate(key):
            press = idx + 1  # 해당 문자를 누르는 데 필요한 횟수

            if char not in key_count:
                key_count[char] = press
            else:
                key_count[char] = min(key_count[char], press)  # 더 적은 횟수로 갱신

    for target in targets:
        total = 0

        for char in target:
            if char not in key_count:
                total = -1  # 만들 수 없는 문자열
                break

            total += key_count[char]

        answer.append(total)

    return answer

---

코드 설명

먼저 결과를 담을 answer 리스트와 문자별 최소 입력 횟수를 저장할 key_count 딕셔너리를 만든다.

answer = []
key_count = {}

answer에는 각 target 문자열을 만들기 위해 필요한 최소 입력 횟수가 들어간다.

key_count에는 각 문자를 입력하기 위한 최소 횟수가 저장된다.

다음으로 keymap을 순회한다.

for key in keymap:
    for idx, char in enumerate(key):
        press = idx + 1

enumerate()를 사용하면 문자의 인덱스와 문자를 동시에 가져올 수 있다.

여기서 인덱스는 0부터 시작하지만, 실제 키를 누르는 횟수는 1부터 시작한다. 그래서 idx + 1을 해서 press에 저장한다.

예를 들어 문자가 0번째에 있으면 1번 눌러야 하고, 2번째에 있으면 3번 눌러야 한다.

그다음 문자가 아직 딕셔너리에 없으면 그대로 저장한다.

if char not in key_count:
    key_count[char] = press

이미 저장된 문자라면 기존 횟수와 새로 찾은 횟수 중 더 작은 값을 저장한다.

else:
    key_count[char] = min(key_count[char], press)

이 부분이 이번 문제의 핵심이다.

같은 문자가 여러 키에 있거나 같은 키 안에 여러 번 등장할 수 있으므로, 항상 최소 입력 횟수를 유지해야 한다.

이제 key_count가 완성되면 targets를 하나씩 확인한다.

for target in targets:
    total = 0

각 target마다 필요한 입력 횟수를 누적해야 하므로 total을 0으로 초기화한다.

그리고 target 안의 문자를 하나씩 확인한다.

for char in target:
    if char not in key_count:
        total = -1
        break

만약 해당 문자가 key_count에 없다면, 자판으로 만들 수 없는 문자라는 뜻이다.

이 경우 해당 target 문자열은 만들 수 없으므로 total을 -1로 바꾸고 반복을 멈춘다.

문자가 존재한다면 해당 문자를 입력하는 데 필요한 최소 횟수를 더한다.

total += key_count[char]

target 하나에 대한 계산이 끝나면 결과를 answer에 추가한다.

answer.append(total)

마지막으로 answer를 반환한다.

return answer

---

풀이 정리

이번 문제는 문자열 자체보다 각 문자별 최소 입력 횟수를 어떻게 관리할 것인지가 핵심이었다.

처음부터 target마다 keymap을 반복해서 찾으려고 하면 코드가 복잡해질 수 있다. 대신 keymap을 먼저 딕셔너리로 정리해두면 이후 계산이 훨씬 단순해진다.

정리하면 이번 풀이의 핵심 구조는 다음과 같다.

문자별 최소 입력 횟수 저장
→ target 문자열 순회
→ 만들 수 있으면 횟수 합산
→ 만들 수 없으면 -1

특히 min()을 사용해서 기존 입력 횟수보다 더 적은 횟수로 갱신하는 부분이 중요했다.

key_count[char] = min(key_count[char], press)

이 한 줄 덕분에 같은 문자가 여러 곳에 등장하더라도 항상 가장 적은 입력 횟수만 남길 수 있었다.

---

3. 나의 간단 소감

오늘 문제는 처음 봤을 때 설명이 살짝 길어서 어렵게 느껴졌다. 휴대폰 자판이라는 상황이 들어가다 보니 문제를 이해하는 데 먼저 시간이 조금 걸렸다.

그런데 핵심을 잡고 보니 결국 문자를 입력하는 최소 횟수를 구하는 문제였다. 같은 문자가 여러 번 나올 수 있으니, 각 문자별로 가장 적은 입력 횟수를 저장해두면 된다는 방향이 보였다.

이번 문제에서 가장 중요했던 건 딕셔너리였다. 문자를 key로 두고, 최소 입력 횟수를 value로 저장하니까 target 문자열을 확인하는 과정이 훨씬 깔끔해졌다.

특히 enumerate()로 인덱스와 문자를 같이 가져오고, idx + 1로 누르는 횟수를 계산하는 흐름이 자연스럽게 연결됐다. 그리고 이미 저장된 문자가 나왔을 때 min()으로 더 작은 값을 남기는 방식도 좋은 포인트였다.

문제를 풀면서 느낀 건, 문자열 문제라고 해서 무조건 문자열만 계속 비교하는 게 아니라는 점이다. 먼저 필요한 정보를 딕셔너리로 정리해두면 이후 로직이 훨씬 단순해진다.

오늘 문제는 복잡한 알고리즘보다는 문제 조건을 잘 읽고, 필요한 정보를 미리 정리하는 방식이 중요했던 문제였다. 앞으로 비슷한 문자열 탐색 문제가 나오면 바로 반복문부터 작성하기보다, 먼저 딕셔너리로 정리할 수 있는 구조인지 확인해봐야겠다.