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

문제

3016. Minimum Number of Pushes to Type Word II

 

영어 소문자로 이루어진 word가 주어진다. 

전화기 키패드의 키들은 영어 소문자로 이루어진 고유한 collection과 매핑돼있다. 

각 키들을 눌러서 word를 만들 수 있다.

예를 들어, 2번 키는 ["a", "b", "c"]와 매핑돼있다. "a"를 누르기 타이핑 하기 위해서는 한 번, "b"를 누르기 위해서는 2번, "c"를 누르기 위해서는 세 번을 누르면 된다.

키들은 수 제한없이 여러 문자로 매핑될 수 있지만, 각 문자는 정확히 하나의 키와 매핑돼야 한다.

 

word를 타이핑 하기 위해 각 키를 remapping하고 눌러야 하는 최소 횟수를 구해라.

(1, *, #, 0은 어떤 문자도 매핑할 수 없다)

풀이 과정

풀이 시간: 20분

알고리즘: 그리디(Greedy)

 

사실상 2~9번 키 어디에 어떤 알파벳을 넣는지는 중요하지 않은 문제다.

word의 등장하는 각 알파벳의 빈도수를 구해서 내림차순 정렬한 후에 배치하면 되는 그리디 문제라고 볼 수 있다. 

어디에 넣든지와 상관없이 가장 많이 등장한 알파벳을 최대한 적게 누르도록 배치하면 된다.

여기서 배치는 정렬 후 가능한 키패드의 개수 8개 이상부터는 어쩔 수 없이 2번, 3번, 4번 ... 누르는 횟수가 증가하기 때문에 8로 나누어 떨어지는 수부터는 누르는 횟수를 증가시킨다.

 

1. 빈도수 계산

2. 내림차순 정렬

3. 그리디 배치

4. 최소 누름 횟수 계산

 

<시간 복잡도>

1. Counter(word): O(n)

2. Sorted: O(nlogn)

3. For 문: O(k)

- k는 고유한 문자의 개수이며, 최악의 경우 n

-> O(n) + O(nlogn) + O(k) = O(nlogn)

코드

from collections import Counter


class Solution:
    def minimumPushes(self, word: str) -> int:
        answer = 0 # word를 만들기 위해 눌러야 하는 최소 횟수
        # 각 알파벳의 빈도수를 구하고, 내림차순으로 정렬
        alpha_freq = sorted(Counter(word).values(), reverse=True)
        push = 1 # 키를 누르는 횟수
        for idx, cnt in enumerate(alpha_freq):
            # 8번째 이후부터는(이미 2~9까지 맨 앞을 다 채웠기 때문에 눌러야 하는 횟수 증가)
            if idx > 0 and idx % 8 == 0:
                push += 1
            answer += push * cnt

        return answer