[2024] day 220. 3016. Minimum Number of Pushes to Type Word II

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 8월 6일 (화)
Leetcode daily problem

3016. Minimum Number of Pushes to Type Word II

https://leetcode.com/problems/minimum-number-of-pushes-to-type-word-ii/?envType=daily-question&envId=2024-08-06

Problem

소문자 영어 문자열 word와 영어 문자의 고유한 컬렉션으로 매핑된 키가 있고 이를 사용해 눌러서 단어를 형성할 수 있는 전화 키패드도 있다.

예를 들어, 키 2는 ["a","b","c"]로 매핑되어 있으며, "a"를 입력하려면 키를 한 번, "b"를 입력하려면 키를 두 번, "c"를 입력하려면 키를 세 번 눌러야 한다.

2~9로 번호가 매겨진 키를 고유한 문자 컬렉션으로 다시 매핑할 수 있. 키는 여러 많은 문자로 다시 매핑할 수 있지만, 각 문자는 정확히 하나의 키에 매핑되어야 한다. 문자열 word를 입력하기 위해 키를 눌러야 하는 최소 횟수를 찾는다.

키를 다시 매핑한 후 word를 입력하는 데 필요한 최소한으로 누르는 횟수를 반환한다.

전화 키패드에서 문자와 키의 매핑에서 1, *, #, 0은 어떤 문자에도 매핑되지 않는다.

Solution

Greedy Sorting

이 문제를 해결하기 위해서 그리디 알고리즘과 정렬을 사용한다.
주어진 문자열에서 가장 빈번하게 등장하는 문자들을 8개의 키(2-9)에 매핑하여, 가능한 최소한의 키 누름으로 모든 문자를 입력하는 것이다.

먼저 주어진 문자열의 각 문자에 대해 빈도를 계산해서, 각 문자가 얼마나 자주 등장하는지 파악하고, 각 문자의 빈도를 내림차순으로 정렬한다.
빈도가 높은 문자일수록 먼저 할당해야 키 누름 횟수를 최소화할 수 있다.

8개의 키가 있다는 것을 고려하여, 빈도 순으로 정렬된 문자들을 8개씩 그룹화한다. 각 그룹은 첫 번째, 두 번째, 세 번째 키 누름을 나타냅니다.그룹 번호는 인덱스를 8로 나눈 몫으로 구한다. 이때 0부터 시작하는 인덱스에 1을 더해서 실제 누름 횟수를 계산하낟.

각 문자에 대해 ((i // 8) + 1) * 빈도를 계산하여, 그 문자를 입력하는 데 필요한 총 키 누름 횟수를 구한다. 여기서 i는 정렬된 빈도 리스트에서의 인덱스이다. 이 값을 모든 문자에 대해 합산하여 최종적으로 필요한 최소한의 키 누름 횟수를 계산한다.

Code

class Solution:
    def minimumPushes(self, word: str) -> int:
        
        freq = [0] * 26
        
        for c in word:
            freq[ord(c)- ord('a')] +=1
            
        freq.sort(reverse=True)
        
        ans = 0
        for i in range(26):
            if freq[i] == 0:
                break
            ans += (i//8+1) * freq[i]
            
        return ans

Complexicity

시간 복잡도

공간 복잡도