[리트코드][Medium] Minimum Number of Pushes to Type Word II

문제

리트코드 Minimum Number of Pushes to Type Word II

문제 풀이 및 회고

10분만에 풀었고 정확하게 생각했지만 몇가지 기록해둘 게 있어서 기록하기 위해 글을 남긴다.

코드(python)

1. 내 풀이

from collections import defaultdict

class Solution(object):
    def minimumPushes(self, word):
        """
        :type word: str
        :rtype: int
        """
        # key - 8 numbers (2~9)
        # one letter to one key
        
        NUM_DICT = defaultdict(lambda:0)
        n = len(word)

        for i in range(n):
            NUM_DICT[word[i]] += 1
        
        if len(NUM_DICT) <= 8: # 가짓수가 8개 이하면 2 ~ 9까지 수 8개 중에 아무거나 배치하고 1씩 늘리면 됨
            return len(word) # 답은 문자 길이
        
        NUM_DICT = sorted(NUM_DICT.items(), key = lambda x:(x[1]), reverse=True) # 1*8 2*... 식으로 갯수 많은거부터 1씩 채워서 1 2 3 4 최대 8개로 하면됨
        answer = 0
        for i in range(len(NUM_DICT)):
            answer += NUM_DICT[i][1] * (i//8 + 1) 
        return answer

from collections import Counter 써도 되는데 저게 거의 2배가량 더 빠름(왜인지 모름 ㄷㄷ 찾아보니 초기화할 때 더 많은 시간이 소요될 수도 있다고 함)

2. 훨씬 빠른 풀이들

class Solution(object):
    def minimumPushes(self, word):
        """
        :type word: str
        :rtype: int
        """
        letters = set(word)
        d = []
        for i in letters:
            d.append(word.count(i))
        count = sorted(d)
        sum = 0
        for i in range(len(count)):
            sum += count[len(count)-i-1] * (i/8 + 1)
        return(sum)

단순히 수 세는 거에서는 set으로 자료형을 바꾸고 list.count가 빠른가봄

궁금한 것들이나 추가 및 수정했으면 좋겠는 거 말해주시면 좋을 거 같아요. 좋은 하루 보내시길 바래요 :)