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 <= 105
- word consists of lowercase English letters.
1. Python
뭐든 한 방에 풀기는 어렵다.
조금 우여곡절이 있었지만, 풀어내는데 성공!
항상 느끼는 건데 Pyton으로 풀면 사고의 범위가 넓어지고, 나머지 언어를 생각하면 굉장히 지엽적으로 변한다
class Solution:
def minimumPushes(self, word: str) -> int:
dic = {}
for x in word:
if x not in dic:
dic[x]=1
else:dic[x]+=1
lst = []
for value,count in dic.items():
lst.append([count,value])
lst.sort(reverse=True)
idx = 0
ans = 0
print(lst)
for x in range(len(lst)):
if x%8==0:
idx+=1
ans += lst[x][0]*idx
return ans
from collections import Counter를 통해 위에 for문을 돌렸던 일련의 과정들을 한 번에 처리할 수도 있다.
just like below!! deque도 collection에 있더만, 은근 collection module에 다양한 method가 많다.
class Solution:
def minimumPushes(self, word: str) -> int:
res = 0
from collections import Counter
counter = Counter(word)
counter_sorted = sorted(counter.values(), reverse=True)
print(counter,counter_sorted)
res = sum(counter_sorted[:8]) + 2*sum(counter_sorted[8:16]) + 3*sum(counter_sorted[16:24]) + 4*sum(counter_sorted[24:])
return res
s=Solution()
s.minimumPushes("aabbccddeeffgghhiiiiii")
2. C
int cmp(const void *a, const void *b) {
return *(int *)b - *(int *)a;
}
int minimumPushes(char* word) {
int cnts[26] = {0};
int idx = 0;
while (word[idx] != '\0') {
cnts[word[idx] - 'a']++;
++idx;
}
qsort(cnts, 26, sizeof(int), cmp);
int total_press = 0;
int press_level = 1;
int letter_idx = 0;
for (int i = 0; i < 26; ++i) {
total_press += cnts[i] * press_level;
letter_idx++;
press_level = (letter_idx + 8) / 8;
}
return total_press;
}
3. C++
#C++
class Solution {
public:
int minimumPushes(string word) {
vector<int> cnts(26);
for (char &c : word) {
cnts[c - 'a']++;
}
sort(cnts.rbegin(), cnts.rend());
int total_press = 0;
int press_level = 1;
int letter_idx = 0;
for (int cnt : cnts) {
total_press += cnt * press_level;
letter_idx++;
press_level = (letter_idx + 8) / 8;
}
return total_press;
}
};
여러 모로 많이 사용되는 C의 qsort이다.