C언어 ] leetCode 3016 - Minimum Number of Pushes to Type Word II

 

 

 

 

leetCode 3016 문제

 

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 <= 10^5 
• word consists of lowercase English letters.

 

 

오랜만에 리트코드에서 C로 풀만한 문제를 찾아봤다.

 

 

문제에서 알 수 있는 전제조건은 다음과 같다.

 

- 알파벳 문자 개수는 26개이다.

- 문자열엔 알파벳 소문자만 등장한다.

- 문자열의 길이는 1~10000 사이이다.

- 문자 배치가 가능한 키패드는 8개이다.

 

 

문자열에 따른 최소 누름횟수를 구하려면 등장빈도가 높은 문자를 키패드의 앞쪽에 배치한다고 보면된다.

 

 

1. 길이가 26인 어레이에 순서대로 알파벳 등장횟수를 기록한다.

 

2. 내림차순으로 정렬한다.

 

3. 가장 많이 등장한 상위 8개 알파벳을 키패드의 첫번째 문자로 등록하고, 그 다음 8개 알파벳을 키패드의 두번째 문자로, 그 다음 8개 알파벳을 키패드의 세번째 문자로, 그 다음 2개 알파벳을 키패드의 네번째 문자로 등록할 것이다. 어레이의 인덱스에 따른 누름횟수는 idx / 8 + 1

 

4. 누름횟수와 등장횟수를 곱해 토탈 누름횟수를 구한다.

 

 

#include <stdio.h>

void sortDescending(int *arr, int size) {
    int i, j, max, temp;
    
    for(i = 0; i < size - 1; i++) {
        max = i;
        for(j = i + 1; j < size; j++) {
            if(arr[j] > arr[max]) max = j;
        }
        temp = arr[i];
        arr[i] = arr[max];
        arr[max] = temp;
    }
}

int minimumPushes(char* word) {
    int count[26] = {0, };
    int ret = 0;
    
    while(*word != 0)
    {        
        int idx = *word - 'a';
        count[idx]++;
        word++;
    }
    
    sortDescending(count, 26);
    
    for(int i = 0; i < 26; i++)
    {
        ret += ((i / 8 + 1) * count[i]);
    }

    return ret;
}

int main()
{
    int ret = minimumPushes("aabbccddeeffgghhiiiiii");
    printf("result = %d\n", ret);
    return 0;
}

 

 

 

 

 

아래는 stdlib.h의 qsort함수를 사용하는 버전으로 바꿔본 것이다. 그런데 코드수행시간이 더 늘어났다.

 

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int*)b - *(int*)a);
}

int minimumPushes(char* word) {
    int count[26] = {0, };
    int ret = 0;
    
    while(*word != 0)
    {        
        int idx = *word - 'a';
        count[idx]++;
        word++;
    }
    
    qsort(count, 26, sizeof(int), compare);
    
    for(int i = 0; i < 26; i++)
    {
        ret += ((i / 8 + 1) * count[i]);
    }

    return ret;
}

int main()
{
    int ret = minimumPushes("aabbccddeeffgghhiiiiii");
    printf("result = %d\n", ret);
    return 0;
}