[리트코드] 3014 - Minimum Number of Pushes to Type Word I

3014. Minimum Number of Pushes to Type Word I

Easy

---

You are given a string word containing distinct 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 = "xycdefghij"
Output: 12
Explanation: The remapped keypad given in the image provides the minimum cost.
"x" -> one push on key 2
"y" -> two pushes on key 2
"c" -> one push on key 3
"d" -> two pushes on key 3
"e" -> one push on key 4
"f" -> one push on key 5
"g" -> one push on key 6
"h" -> one push on key 7
"i" -> one push on key 8
"j" -> one push on key 9
Total cost is 1 + 2 + 1 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 12.
It can be shown that no other mapping can provide a lower cost.

 

Constraints:

• 1 <= word.length <= 26
• word consists of lowercase English letters.
• All letters in word are distinct.

분류

수학, 문자열, 그리디

---

문제 풀이

문제 분석

이 문제는 전화 키패드의 키를 재배열하여 주어진 단어 word를 입력하는 데 필요한 총 푸시 횟수를 최소화하는 것을 목표로 합니다.

• 입력: word (소문자 영어 알파벳으로 구성된 문자열, 모든 문자는 서로 다름).
• 출력: 단어를 입력하는 데 필요한 최소 푸시 횟수 (정수).
• 핵심 규칙:
  • 전화 키패드에는 숫자 2부터 9까지 총 8개의 키가 있습니다.
  • 각 키에는 원하는 만큼의 문자를 할당할 수 있습니다.
  • 각 문자는 정확히 하나의 키에 할당되어야 합니다.
  • 키에 할당된 문자를 입력하는 데 필요한 푸시 횟수는 해당 문자가 키에 할당된 순서에 따라 결정됩니다: 첫 번째 문자는 1번 푸시, 두 번째 문자는 2번 푸시, 세 번째 문자는 3번 푸시 등.
• 제약 조건: word의 길이는 1에서 26 사이이며, 모든 문자는 서로 다릅니다.

문제는 8개의 키 슬롯이 있고, 각 슬롯에 문자를 할당할 때 1번째 문자는 1 푸시, 2번째 문자는 2 푸시 등 비용이 증가한다는 점에 주목해야 합니다. word에 있는 모든 문자가 서로 다르다는 제약 조건이 중요합니다.

접근 방법

주어진 단어를 입력하는 데 필요한 총 푸시 횟수를 최소화하려면, 가장 적은 푸시 횟수를 요구하는 위치(즉, 1 푸시 위치)에 최대한 많은 문자를 할당해야 합니다. 그 다음으로는 2 푸시 위치, 3 푸시 위치 순으로 할당해야 합니다. 이는 전형적인 그리디(Greedy) 접근 방식입니다.

1. 가장 낮은 비용 먼저: 1 푸시가 가장 저렴한 비용이므로, 1 푸시 슬롯에 문자를 먼저 할당합니다.
2. 8개 키 활용: 8개의 키가 있으므로, 각 키에 1 푸시 위치 하나씩, 총 8개의 1 푸시 슬롯을 활용할 수 있습니다.
3. 순차적 할당: 8개의 1 푸시 슬롯이 모두 채워지면, 다음 8개의 문자는 각 키의 2 푸시 슬롯에 할당되어야 합니다. 그 다음은 3 푸시 슬롯 등 순서대로 진행합니다.

따라서, word에 있는 모든 문자를 순서대로 가져와서, 처음 8개 문자는 1 푸시, 그 다음 8개 문자는 2 푸시, 그 다음 8개 문자는 3 푸시로 비용을 계산하면 됩니다. word의 모든 문자가 distinct(서로 다름)하기 때문에, word에 어떤 문자가 있든 모든 문자의 빈도수는 1입니다. 따라서 특정 문자의 빈도수를 고려할 필요 없이 단순히 word의 길이와 8개의 키를 기준으로 순차적으로 푸시 횟수를 늘려가면 됩니다.

구현 설명

이 코드는 주어진 단어 word의 각 문자에 대해 최소 푸시 횟수를 계산합니다.

1단계: 문자 빈도수 계산 및 정렬 (형식적 단계)

• count = Counter(word): collections.Counter를 사용하여 word에 포함된 각 문자의 빈도수를 계산합니다. 문제의 제약 조건('모든 문자는 서로 다름') 때문에 모든 문자의 빈도수는 항상 1이 됩니다. 예를 들어 word = "abc"라면 {'a': 1, 'b': 1, 'c': 1}이 됩니다.
• count_list = sorted(count.items(), key = lambda x:-x[1]): 계산된 빈도수를 기준으로 내림차순으로 정렬합니다. 하지만 위에서 설명했듯이 모든 빈도수가 1이므로, 이 정렬은 실제 푸시 횟수 계산 결과에 영향을 주지 않습니다. 이 부분은 일반적으로 더 복잡한 문제(예: 중복 문자가 허용되고, 빈도수가 높은 문자를 더 적은 푸시 횟수에 할당해야 할 때)에 대비한 일반적인 그리디 패턴입니다. 여기서는 단순히 word에 있는 각 문자를 순서대로 처리하는 것과 같습니다.

2단계: 총 푸시 횟수 계산을 위한 변수 초기화

• cnt = 0: 현재 푸시 레벨(예: 1 푸시, 2 푸시 등)에 할당된 문자의 개수를 추적하는 변수입니다. 0으로 초기화됩니다.
• idx = 1: 현재 문자를 할당할 때 필요한 푸시 횟수를 나타내는 변수입니다. 1 푸시부터 시작하므로 1로 초기화됩니다.
• answer = 0: 단어 전체를 입력하는 데 필요한 총 푸시 횟수를 누적할 변수입니다. 0으로 초기화됩니다.

3단계: 문자 할당 및 푸시 횟수 계산

• for x,y in count_list:: 정렬된 count_list의 각 항목(x: 문자, y: 빈도수. 여기서 y는 항상 1)에 대해 반복합니다.
  • answer += idx * y: 현재 문자를 입력하는 데 필요한 푸시 횟수(idx)에 해당 문자의 빈도수(y)를 곱하여 answer에 더합니다. y가 항상 1이므로, answer += idx와 같습니다.
  • cnt += 1: 현재 푸시 레벨에 할당된 문자의 개수를 1 증가시킵니다.
  • if cnt == 8:: 만약 현재 푸시 레벨(idx)에 8개의 문자(각 키에 하나씩)가 모두 할당되었다면, 다음 푸시 레벨로 전환해야 합니다.
    • cnt = 0: 다음 푸시 레벨을 위해 cnt를 0으로 리셋합니다.
    • idx += 1: 푸시 횟수를 1 증가시킵니다 (예: 1 푸시에서 2 푸시로, 2 푸시에서 3 푸시로).

4단계: 결과 반환

• return answer: 모든 문자에 대한 푸시 횟수 계산이 끝나면, answer에 누적된 최종 총 푸시 횟수를 반환합니다.

⏱복잡도 분석

• 시간 복잡도: O(L log L)

  • Counter(word)는 word의 길이 L에 비례하는 시간을 소모합니다: O(L).
  • sorted(count.items(), ...)는 word 내 고유 문자의 개수(최대 L개)를 정렬하는 데 O(L log L) 시간을 소모합니다. 문제의 제약 조건(L <= 26)을 고려하면, 이는 사실상 상수 시간 O(1)으로 볼 수 있습니다.
  • for 루프는 word 내의 각 고유 문자(최대 L개)에 대해 한 번씩 실행되므로 O(L) 시간을 소모합니다.
  • 따라서 전체 시간 복잡도는 O(L + L log L + L) = O(L log L) 입니다.

• 공간 복잡도: O(L)

  • Counter(word)는 word 내의 각 고유 문자와 그 빈도수를 저장하는 데 O(L) 공간을 소모합니다.
  • count_list는 정렬된 문자-빈도수 쌍을 저장하는 데 O(L) 공간을 소모합니다.
  • 문제의 제약 조건(L <= 26)을 고려하면, 이는 사실상 상수 공간 O(1)으로 볼 수 있습니다.
  • 따라서 전체 공간 복잡도는 O(L) 입니다.

핵심 포인트

1. 그리디 전략: 가장 적은 푸시 횟수를 요구하는 슬롯(1 푸시, 그 다음 2 푸시 등)에 문자를 우선적으로 할당하는 그리디 전략이 최적의 해를 보장합니다.
2. 8개 키의 활용: 사용 가능한 8개의 키(2-9)는 각 푸시 레벨(1 푸시, 2 푸시 등)에서 8개의 문자를 할당할 수 있는 공간을 제공합니다. 8개 문자가 할당될 때마다 다음 푸시 레벨로 전환해야 합니다.
3. "모든 문자가 서로 다름" 제약 조건: 이 문제에서는 word의 모든 문자가 서로 다르므로, 모든 문자의 빈도수는 1입니다. 따라서 Counter와 빈도수 기반 정렬은 실제로 푸시 횟수 계산에 영향을 주지 않으며, 단순히 word의 길이에 따라 순차적으로 푸시 횟수를 늘려가며 계산하는 것과 동일한 결과를 줍니다. 하지만 이는 유사한 종류의 문제(예: 중복 문자가 있는 경우)에 대비한 일반적인 접근 방식이므로 코드에 포함되어 있습니다.

풀이 코드

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