[리트코드] 3016 - Minimum Number of Pushes to Type Word II

3016. Minimum Number of Pushes to Type Word II

Medium

---

You are given a string word containing lowercase English letters.

Telephone keypads have keys mapped with distinct collections of lowercase English letters, which can be used to form words by pushing them. For example, the key 2 is mapped with ["a","b","c"], we need to push the key one time to type "a", two times to type "b", and three times to type "c" .

It is allowed to remap the keys numbered 2 to 9 to distinct collections of letters. The keys can be remapped to any amount of letters, but each letter must be mapped to exactly one key. You need to find the minimum number of times the keys will be pushed to type the string word.

Return the minimum number of pushes needed to type word after remapping the keys.

An example mapping of letters to keys on a telephone keypad is given below. Note that 1, *, #, and 0 do not map to any letters.

 

Example 1:

Input: word = "abcde"
Output: 5
Explanation: The remapped keypad given in the image provides the minimum cost.
"a" -> one push on key 2
"b" -> one push on key 3
"c" -> one push on key 4
"d" -> one push on key 5
"e" -> one push on key 6
Total cost is 1 + 1 + 1 + 1 + 1 = 5.
It can be shown that no other mapping can provide a lower cost.

Example 2:

Input: word = "xyzxyzxyzxyz"
Output: 12
Explanation: The remapped keypad given in the image provides the minimum cost.
"x" -> one push on key 2
"y" -> one push on key 3
"z" -> one push on key 4
Total cost is 1 * 4 + 1 * 4 + 1 * 4 = 12
It can be shown that no other mapping can provide a lower cost.
Note that the key 9 is not mapped to any letter: it is not necessary to map letters to every key, but to map all the letters.

Example 3:

Input: word = "aabbccddeeffgghhiiiiii"
Output: 24
Explanation: The remapped keypad given in the image provides the minimum cost.
"a" -> one push on key 2
"b" -> one push on key 3
"c" -> one push on key 4
"d" -> one push on key 5
"e" -> one push on key 6
"f" -> one push on key 7
"g" -> one push on key 8
"h" -> two pushes on key 9
"i" -> one push on key 9
Total cost is 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 2 * 2 + 6 * 1 = 24.
It can be shown that no other mapping can provide a lower cost.

 

Constraints:

• 1 <= word.length <= 105
• word consists of lowercase English letters.

분류

해시 테이블, 문자열, 그리디, 정렬, 카운팅

---

문제 풀이

문제 분석

이 문제는 주어진 문자열 word를 입력하기 위해 전화 키패드(2~9번 키)의 문자 매핑을 최적으로 재배열했을 때, 필요한 최소 키 누름 횟수를 구하는 문제입니다.

• 입력: 소문자 알파벳으로 이루어진 문자열 word (길이 최대 100,000)
• 출력: 최적의 키 매핑 후 word를 타이핑하는 데 필요한 최소 푸시 횟수 (정수)
• 제약 조건:
  • 키 2~9번까지 총 8개의 키를 사용할 수 있습니다.
  • 각 키에는 여러 문자를 할당할 수 있으며, 한 키의 첫 번째 문자는 1번, 두 번째는 2번, ... 누르면 입력됩니다.
  • 모든 알파벳은 정확히 하나의 키에만 매핑되어야 합니다.

---

접근 방법

이 문제는 **탐욕 알고리즘(Greedy Algorithm)**과 **정렬(Sorting)**을 사용하여 해결합니다.

핵심 아이디어:

• 자주 등장하는 문자는 적게 눌러서 입력할 수 있는 위치(키의 첫 번째 위치)에 배치해야 전체 누름 횟수가 최소가 됩니다.
• 키는 8개(2~9번)가 있으므로, **가장 빈도가 높은 상위 8개 문자는 각 키의 첫 번째 위치(1번 누름)**에 배치합니다.
• 그다음으로 빈도가 높은 8개 문자는 각 키의 두 번째 위치(2번 누름)에 배치하는 식으로 진행합니다.

사용 자료구조:

• Counter (해시 맵): 각 문자의 출현 빈도를 O(N)에 계산하기 위해 사용.
• 리스트: 빈도 수 기준으로 내림차순 정렬을 위해 사용.

---

구현 설명

1. 문자 빈도 수 계산 및 정렬

count = Counter(word)
count_list = sorted(count.items(), key=lambda x: -x[1])

• Counter(word)를 이용해 word 내 각 알파벳의 출현 횟수를 딕셔너리 형태로 구합니다.
• sorted(..., key=lambda x: -x[1])로 빈도 수(x[1]) 기준 내림차순 정렬된 리스트 count_list를 만듭니다. 이제 가장 많이 쓰이는 문자부터 순서대로 처리할 수 있습니다.

2. 누름 횟수(가중치) 결정 로직

cnt = 0
idx = 1
answer = 0

• idx: 현재 문자가 키에서 몇 번째 위치에 배정될지 나타내는 **가중치(누름 횟수)**입니다. 처음에는 1(첫 번째 위치)부터 시작합니다.
• cnt: 현재 가중치 idx로 몇 개의 문자를 처리했는지 세는 카운터입니다. 8개가 채워지면 다음 가중치로 넘어가야 합니다.

3. 정렬된 리스트 순회하며 총 누름 횟수 누적

for x, y in count_list:
    answer += idx * y
    cnt += 1
    if cnt == 8:
        cnt = 0
        idx += 1

• 정렬된 리스트((문자, 빈도))를 순회합니다.
• 현재 문자 x의 빈도 y에 현재 가중치 idx를 곱해 answer에 더합니다. (예: 빈도 5인 문자가 2번 눌러야 하는 위치라면 5 * 2 = 10 추가)
• cnt를 1 증가시키고, 8개가 다 차면(cnt == 8) cnt를 0으로 초기화하고 idx를 1 증가시킵니다. 이는 다음 8개 문자가 키의 다음 위치(한 번 더 눌러야 하는 위치)에 배정됨을 의미합니다.

4. 결과 반환

• 모든 문자를 처리한 후 누적된 answer를 반환합니다.

---

⏱복잡도 분석

• 시간 복잡도: O(N + M log M) → O(N)

  • N: word의 길이 (최대 100,000)
  • M: word에 등장하는 고유 문자의 수 (최대 26, 알파벳 소문자)
  • Counter 생성: O(N)
  • 정렬: 고유 문자는 최대 26개이므로 O(26 log 26) = O(1) 상수 시간으로 처리됩니다.
  • 순회: O(M) = O(1)
  • 따라서 전체 시간 복잡도는 입력 크기 N에 선형인 **O(N)**입니다.

• 공간 복잡도: O(M) → O(1)

  • Counter와 정렬 리스트에 고유 문자 수만큼의 공간이 필요합니다.
  • 알파벳 소문자는 26개로 고정되어 있으므로 O(1) 상수 공간입니다.

---

핵심 포인트

1. 빈도수 높은 문자에 낮은 비용 할당: 전체 비용을 최소화하려면 자주 쓰이는 문자를 적게 누르는 위치(1번)에 배치하는 그리디 전략이 최적입니다. 이는 '가장 큰 값에 가장 작은 가중치를 곱해야 합이 최소가 된다'는 재배열 부등식(Rearrangement Inequality) 원리와 같습니다.
2. 키 8개의 제약 조건 활용: 키가 8개(2~9번)이므로, 가중치 1자리는 최대 8개 문자까지, 가중치 2자리는 그다음 8개 문자까지 배정 가능합니다. 카운터(cnt)를 이용해 8개 단위로 가중치(idx)를 증가시키는 로직이 핵심입니다.
3. 상수 시간 정렬 가능: 알파벳 소문자는 26개로 종류가 한정되어 있으므로, 정렬 복잡도 O(26 log 26)를 상수 시간으로 간주하여 전체 알고리즘을 O(N) 선형 시간에 해결할 수 있습니다.

풀이 코드

from collections import Counter

class Solution:
    def minimumPushes(self, word: str) -> int:
        count = Counter(word)
        count_list = sorted(count.items(), key = lambda x:-x[1])
        cnt = 0
        idx = 1
        answer = 0
        for x,y in count_list:
            answer += idx * y
            cnt += 1
            if cnt == 8:
                cnt = 0
                idx += 1

        return answer