(Python3) - LeetCode (Easy) : 3014. Minimum Number of Pushes to Type Word I

https://leetcode.com/problems/minimum-number-of-pushes-to-type-word-i

Minimum Number of Pushes to Type Word I - LeetCode

비둘기집 원리를 생각해 풀 수 있었던 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

📑 key 배정하는 것을 word의 한 문자를 누르는 비용이라고 생각하고 assign과 배정을 위해 남은 word의 길이 remaining, 정답 ans를 선언해주고 각각 최소 1번 눌러야하므로 1을, word의 현재 길이를, 0을 배정합니다

📔 풀이과정

📑 비둘기집의 원리
2 ~ 9까지의 패드에만 key 배정이 가능하므로 8자가 넘는 word는 골고루 배치한다고 쳤을때 첫 8자는 1번씩만 누를 수 있게 배치하게 되면 그 다음 문자부터는 2번씩 누르도록 배치할 수 밖에 없습니다. 순차적으로 8자씩 배치할 때 눌러야할 패드의 수 또한 1개씩 사용자가 눌러야 합니다.

📑 루프 제한
remaining // 8 만큼 loop를 돌아 8자씩 배정하며 매 루프마다 ans는 8*assign만큼 누적해 더해주며 assign을 1씩 증가시킵니다.

📑 시간 복잡도

O(1): 26자가 최대이기 때문입니다

📑 공간 복잡도

O(1): 변수 4개만 선언하기 때문입니다

📔 정답 출력 | 반환

ans를 반환합니다.

---

📕 Code

📔 Python3

class Solution:
    def minimumPushes(self, word: str) -> int:
        assign = 1
        remaining = len(word)
        ans = 0
        loop = remaining // 8
        for _ in range(loop):
            remaining -= 8
            ans += 8 * assign
            assign += 1
        ans += remaining * assign
        return ans

 

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.