[백준] 14254. 비밀번호 변경 - Python

[Gold V]

 

https://www.acmicpc.net/problem/14254

14254번: 비밀번호 변경

 

풀이

우선 전체 길이의 1/2 보다 K가 작다면, 그냥 똑같이 맞춰주면 되므로 크게 어렵지 않다.

전체 길이의 1/2 보다 K가 클 때가 문제인데, 겹치는 부분의 어느 한 값을 바꾸면, 앞의 k개와 뒤의 k개로 나누었을 때 두 쪽 모두 영향을 받기 때문이다.

따라서, 겹치는 부분은 항상 팰린드롬(Palindrome) 이 된다.

---

겹치는 부분 말고, 다른 부분들로부터 생각해 보자.

abckv adf akgef
8

위와 같은 경우, 앞부분은 abckvadf, 뒷부분은 adfakgef 이다.

앞 부분에서 겹치는 부분을 제외하면 abckv. 이는 뒷부분의 앞 5자리와 동일해야 하므로,

(6~10)번째 알파벳은 (길이-k)번째 전의 알파벳 (1~5)번째 알파벳과 같아야 하는 것이고,

또한 (11~13)번째는 다시 (6~8)번째 알파벳과 같아야 하므로, (1~3)번째 알파벳과 같아야 한다.

 

따라서, (길이-k)개 간격으로 알파벳이 같아야 한다는 것이며,

변경하는 알파벳이 적어야 하므로, (길이-k)간격으로 알파벳의 개수를 세어 가장 많은 알파벳을 기준으로 삼아 변경한다.

 

past = input()
k = int(input())

front = past[:k]
back = past[-k:]

res = 0

if len(past)/2 >= k:
    for i in range(k):
        if front[i] != back[i]:
            res += 1
else:
    # 간격 n
    n = len(past)-k

    for i in range(n):
        p = i
        cnt = dict()
        while p < len(past):
            if cnt.get(past[p]):
                cnt[past[p]] += 1
            else:
                cnt[past[p]] = 1

            p += n

        # 최대인 key값
        m = max(cnt, key=cnt.get)
        for key in cnt.keys():
            if key == m:
                continue
            res += cnt[key]

print(res)