[LeetCode] 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

leetcode - 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.

 

영문 알파벳 소문자로 이루어진 문자열 word가 주어진다.

전화 키패드는 영어 소문자로 매핑될 수 있는데, 여러 번 누름에 따라서 매핑된 값이 바뀔 수 있다.

매핑은 2~9에서만 가능하고, 당신의 마음대로 매핑가능하다.

 

word를 입력하기 위한 최소 타이핑 횟수를 구하시오.

 

풀이

1번 눌러서 매핑되는 글자는 최대 8개,

2, 3번 역시 8개,

마지막으로, 4번 눌러서 매핑되는 글자는 2개이다.

 

각 글자에 대한 빈도를 배열에 담아서, 내림차순 정렬한 뒤,

앞쪽 8개부터 누름횟수(1)를 곱해서 더하고,

그 다음 8개로 누름횟수(2)를 곱해서 누적하고,

그 다음 8개로 누름횟수(3)를 곱해서 누적하고,

마지막 2개도 각각 누름횟수(4)를 곱해서 누적한다.

그 누적된 횟수를 반환하면 된다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int minimumPushes(string word) {
        vector<int> freq(26, 0);
        for(const auto &letter : word) {
            freq[letter - 'a']++;
        }

        sort(freq.begin(), freq.end(), greater<int>());
        int ans = 0;
        int pushCount = 1;

        for(int i = 0; i < 8; i++) {
            ans += freq[i] * pushCount;
        }
        pushCount++;
        for(int i = 8; i < 16; i++) {
            ans += freq[i] * pushCount;
        }
        pushCount++;
        for(int i = 16; i < 24; i++) {
            ans += freq[i] * pushCount;
        }
        pushCount++;
        for(int i = 24; i < 26; i++) {
            ans += freq[i] * pushCount;
        }

        return ans;
    }
};