[Leetcode] 3016. Minimum Number of Pushes to Type Word II

문제 요약

• 알고리즘 분류:  그리디, , 정렬, Counting
• 난이도: Medium
• 문제내용:
  • 각 키(2~9)는 서로 다른 알파벳 집합에 매핑될 수 있습니다.
  • 키는 어떤 개수의 문자로든 재매핑할 수 있습니다.
  • 각 알파벳은 정확히 하나의 키에만 매핑되어야 합니다.
  • 키에 매핑된 n번째 문자를 입력하려면 키를 n번 눌러야 합니다.
    • 예: 키 '2'에 ['a','b','c']가 매핑되면, 'a'는 1번, 'b'는 2번, 'c'는 3번 눌러야 합니다.
  • 주어진 단어 word를 입력하기 위한 최소 키 누름 횟수를 반환하세요.
• 사이트 주소: https://leetcode.com/problems/minimum-number-of-pushes-to-type-word-ii/description/

문제풀이

이번 문제에서는 완전탐색으로 풀수 있지만 최대 크기가 10^5인점으로 고려하면 다른 방법으로 풀어야 한다. 그래서 이번에는 그리디로 풀어야 통과가 될것이다. 그리디에 설명은 아래 글에서 확인 해보면 된다.

https://jih3508.tistory.com/70

[알고리즘 이론] 그리디(Greedy)

문제 접근 방법

이 문제의 핵심은 다음과 같습니다:

1. 어떤 문자를 어떤 키에 할당할 것인가?
2. 각 키 내에서 문자의 순서는 어떻게 배치할 것인가?

최적의 전략을 생각해보면:

1. 자주 사용되는 문자는 적은 횟수로 입력할 수 있어야 합니다 - 빈도수가 높은 문자는 1번만 눌러서 입력할 수 있게 해야 합니다.
2. 키의 개수는 제한되어 있습니다 - 우리가 사용할 수 있는 키는 2~9까지 총 8개입니다.
3. 각 키에 할당된 문자의 수에 따라 누르는 횟수가 달라집니다 - 키에 3개의 문자가 있으면, 첫 번째 문자는 1번, 두 번째는 2번, 세 번째는 3번 눌러야 합니다.

이런 조건을 고려할 때, 최적의 전략은 빈도수가 높은 문자부터 각 키의 앞쪽에 배치하는 것입니다.

💡 알고리즘 설계

이 문제의 해결 방법은 다음과 같습니다:

1. 단어에서 각 알파벳의 빈도수를 계산합니다.
2. 빈도수를 기준으로 알파벳을 정렬합니다(빈도가 높은 것부터).
3. 빈도가 가장 높은 문자부터 순서대로 키에 할당합니다:
   • 첫 8개 문자는 각 키(2~9)의 첫 번째 위치에 배치 (1번씩 눌러 입력)
   • 다음 8개 문자는 각 키의 두 번째 위치에 배치 (2번씩 눌러 입력)
   • 그 다음 8개 문자는 각 키의 세 번째 위치에 배치 (3번씩 눌러 입력)
   • 나머지 문자들도 같은 방식으로 배치합니다.

🧮 예시를 통한 이해

단어 "hello"를 예로 들어보겠습니다:

1. 빈도수 계산:
   • 'h': 1번
   • 'e': 1번
   • 'l': 2번
   • 'o': 1번
2. 빈도수 정렬 (오름차순):
   • [0, 0, 0, 0, ... 0, 1, 1, 1, 2] (빈도수가 0인 문자들 + 'e', 'h', 'o', 'l')
3. 최적 배치 계산:
   • 'l'(빈도수 2): 1번 키의 첫 번째 위치 → 2 × 1 = 2번 누름
   • 'e', 'h', 'o'(각 빈도수 1): 2, 3, 4번 키의 첫 번째 위치 → 각 1 × 1 = 3번 누름
4. 총 누름 횟수: 2 + 3 = 5번

마무리

 위와 같이 구현 하면 시간 복잡도는 O(N)만큼 나온다. 카운터와 정렬 들어가면 O(NlogN)인데.. 크기가 26가 고정이라서 의미가 없다. 그래서 문자열 길이 N만큼 걸린다고 보면된다.

Code

Python

class Solution:
    def minimumPushes(self, word: str) -> int:
        
        # 알파벳 빈도수를 저장할 배열 초기화 (26개의 알파벳)
        count = [0 for _ in range(26)]

        # 입력 문자열의 각 문자에 대한 빈도수 계산
        for alphabet in word:
            count[ord(alphabet) - ord('a')] += 1 # 'a'를 빼서 인덱스로 변환 (a=0, b=1, ...)

        # 빈도수 배열을 오름차순으로 정렬
        count.sort(reverse=True)

        # 최소 푸시 횟수 계산
        result = 0
        for i in range(26):
            #  빈도수가 높은 문자부터 처리 (뒤에서부터 접근)
            # i/8 + 1은 몇 번째 키 위치인지 계산 (첫 8개는 1번 누름, 다음 8개는 2번 누름, ...)
            result += count[i] * (i // 8 + 1)

        return result

Counter

파이썬에는 Conter라는 모듈을 제공 해준다.

from collections import Counter

class Solution(object):
    def minimumPushes(self, word):
        
        count = Counter(word)
        return sum([cnt * (i // 8 + 1) for i, cnt in enumerate(sorted(count.values(), reverse=True))])

 

Java

class Solution {
    public int minimumPushes(String word) {

        // 알파벳 빈도수를 저장할 배열 초기화 (26개의 알파벳)
        int[] count = new int[26];

        // 입력 문자열의 각 문자에 대한 빈도수 계산
        for(char alphabet : word.toCharArray()){
            count[alphabet - 'a']++; // 'a'를 빼서 인덱스로 변환 (a=0, b=1, ...)
        }

        // 빈도수 배열을 오름차순으로 정렬
        Arrays.sort(count);

        // 최소 푸시 횟수 계산
        int result = 0;
        for(int i = 0; i < 26; i++){
            // 빈도수가 높은 문자부터 처리 (뒤에서부터 접근)
            // i/8 + 1은 몇 번째 키 위치인지 계산 (첫 8개는 1번 누름, 다음 8개는 2번 누름, ...)
            result += count[26 - i - 1] * (i / 8 + 1);
        }

        return result;
    }
}

Javascript

var minimumPushes = function(word) {
    
    // 알파벳 빈도수를 저장할 배열 초기화 (26개의 알파벳)
    let count = Array(26).fill(0);

    // 입력 문자열의 각 문자에 대한 빈도수 계산
    for(const alphabet of word) {
       count[alphabet.charCodeAt() - 'a'.charCodeAt()]++; // 'a'를 빼서 인덱스로 변환 (a=0, b=1, ...)
    }

    // 빈도수 배열을 오름차순으로 정렬
    count.sort((a, b) => b - a);

    // 최소 푸시 횟수 계산
    let result = 0;

    for(let i = 0; i < 26; i++){
        // 빈도수가 높은 문자부터 처리 (뒤에서부터 접근)
        // i/8 + 1은 몇 번째 키 위치인지 계산 (첫 8개는 1번 누름, 다음 8개는 2번 누름, ...)
        result += count[i] * (Math.floor(i / 8) + 1);
    }

    return result;
};