[Leetcode]3137. Minimum Number of Operations to Make Word K-Periodic

문제 요약

• 알고리즘 분류: 문자열, 해쉬
• 난이도: Medium
• 문제내용:
  • 문자열 word와 k 정수가 준다.
  • word k길이로 나눈것을 a,b,c, a ... 라고 하면 나눈것을 a, ,a , a...로 같은 반복된 문자열로 할라면 최소 몇개만 바꾸면 될지 반환 하여라
• 사이트 주소: https://leetcode.com/problems/minimum-number-of-operations-to-make-word-k-periodic/description/

문제풀이 

 이번 문제는 k길이 등분해서 abc패턴을 aaa로 만드는데 최소 몇번 해야 하는지만 알면 되는 문제이다. 

각 k길이 만큼 나눠서 모든 경우의 수를 구하도 되지만 간단 하게 생각하면 각 문자열 자른 것을 몇번  반복된것을 구해서 전체개수에서 가장 많은것을 빼면 되는 것이다. 자세한것은 아래 코드를 보면 된다.

Code

 아래 처럼 구현하면 시간 복잡도는 O(N)만큼 나올 것이다.

Python

class Solution:
    def minimumOperationsToMakeKPeriodic(self, word: str, k: int) -> int:
        token = dict({})
        length = len(word)
        for i in range(0, length, k):
            strToken = word[i:i+k]
            # 없는 경우 단어추가한다.
            if strToken not in token.keys():
                token[strToken] = 0
            token[strToken] += 1

        # 가장 많이 나온것을 뺀다.
        return length // k - max(token.values())

Java

class Solution {
    public int minimumOperationsToMakeKPeriodic(String word, int k) {
        Map<String, Integer> token = new HashMap<>();
        int length = word.length();

        for (int i = 0; i < length; i += k) {
            String tokenWord =  word.substring(i, i + k);
            // 잘라낸 단어가 없을 경우 추가 한다.
            if(!token.containsKey(tokenWord)){
                token.put(tokenWord, 0);
            }
            // 잘라낸 단어 +1 추가한다.
            token.put(tokenWord, token.get(tokenWord) + 1);
        }
        
        // 자르는 수와 가장 많이 나온 갯수를 뺀다.
        return  length / k - token.values().stream().mapToInt(x -> x).max().getAsInt();
    }
}