Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 구현하는 강력한 비밀번호 검사기 – 최소 변경 횟수 계산 알고리즘

문제 정의

하나의 문자열, 즉 비밀번호가 주어졌을 때 이를 강력한(strong) 비밀번호로 만들기 위해 필요한 최소 변경 횟수를 구하는 문제입니다. 강력한 비밀번호는 아래 세 가지 조건을 모두 충족해야 합니다.

  • 길이 조건: 최소 6자 이상, 최대 20자 이하여야 합니다.
  • 문자 종류 조건: 소문자, 대문자, 숫자를 각각 최소 하나씩 포함해야 합니다.
  • 반복 조건: "aaa", "PPP", "888"처럼 같은 문자가 세 번 연속으로 나타나서는 안 됩니다.

예를 들어 입력이 "aa26bbb"라고 해보겠습니다. 이 문자열에는 대문자가 없고 'b'가 세 번 연속 등장하므로 최소 한 번의 변경이 필요합니다. 'b' 하나를 대문자로 바꾸면 두 가지 문제를 동시에 해결할 수 있습니다.

알고리즘 접근 방법

이 문제는 그리디(greedy) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  1. 먼저 어떤 문자 종류(소문자·대문자·숫자)가 빠져 있는지 확인합니다.
  2. 같은 문자가 3개 이상 연속되는 구간을 찾아, 해당 구간을 고치는 데 필요한 교체(replace) 횟수를 셉니다.
  3. 문자열 길이에 따라 세 가지 경우로 나누어 처리합니다.

단계별 풀이

  1. missing_type을 3으로 초기화합니다.
  2. 소문자가 하나라도 있으면 missing_type을 1 감소시킵니다.
  3. 대문자가 하나라도 있으면 missing_type을 1 감소시킵니다.
  4. 숫자가 하나라도 있으면 missing_type을 1 감소시킵니다.
  5. change = 0, one = 0, two = 0으로 초기화하고 인덱스 p는 2부터 시작합니다.
  6. p가 문자열 길이보다 작은 동안 다음을 반복합니다.
    • s[p], s[p-1], s[p-2]가 모두 같다면(연속 3개 이상 구간):
      • length를 2로 설정합니다.
      • 연속 구간이 끝날 때까지 length를 1씩 늘리고 p를 전진시킵니다.
      • change에 length // 3을 더합니다. (연속 n개를 고치려면 최소 n//3번의 교체가 필요)
      • length가 3으로 나누어떨어지면 one을 1 증가시킵니다.
      • length를 3으로 나눈 나머지가 1이면 two를 1 증가시킵니다.
    • 그렇지 않으면 p를 1 증가시킵니다.
  7. 문자열 길이가 6 미만이면 max(missing_type, 6 - len(s))를 반환합니다. (부족한 길이만큼 문자를 추가하거나 누락된 종류를 보완)
  8. 문자열 길이가 20 이하이면 max(missing_type, change)를 반환합니다.
  9. 길이가 20을 초과하는 경우:
    • delete = len(s) - 20: 제거해야 할 문자 수입니다.
    • change -= min(delete, one)
    • change -= min(max(delete - one, 0), two * 2) / 2
    • change -= max(delete - one - 2 * two, 0) / 3
  10. 최종적으로 delete + max(missing_type, change)를 반환합니다.

여기서 one과 two는 각각 "길이가 3의 배수인 연속 구간"과 "3으로 나눈 나머지가 1인 연속 구간"의 개수를 의미합니다. 삭제(delete)와 교체(replace)를 어떻게 조합하느냐에 따라 필요한 연산 횟수가 달라지므로, 이 정보를 활용해 최적의 조합을 찾습니다. 전체 시간 복잡도는 O(n)으로 매우 효율적입니다.

파이썬 구현 예제

class Solution(object):
   def strongPasswordChecker(self, s):
      missing_type = 3
      if any('a' <= c <= 'z' for c in s): missing_type -= 1
      if any('A' <= c <= 'Z' for c in s): missing_type -= 1
      if any(c.isdigit() for c in s): missing_type -= 1

      change = 0
      one = two = 0
      p = 2
      while p < len(s):
         if s[p] == s[p-1] == s[p-2]:
            length = 2
            while p < len(s) and s[p] == s[p-1]:
               length += 1
               p += 1
            change += length / 3
            if length % 3 == 0: one += 1
            elif length % 3 == 1: two += 1
         else:
            p += 1

      if len(s) < 6:
         return max(missing_type, 6 - len(s))
      elif len(s) <= 20:
         return max(missing_type, change)
      else:
         delete = len(s) - 20
         change -= min(delete, one)
         change -= min(max(delete - one, 0), two * 2) / 2
         change -= max(delete - one - 2 * two, 0) / 3
         return delete + max(missing_type, change)

ob = Solution()
print(ob.strongPasswordChecker('aa26bbb'))

실행 결과

입력

"aa26bbb"

출력

1

결과 해석

입력 "aa26bbb"에는 소문자와 숫자는 있지만 대문자가 없고, 'b'가 세 번 연속 등장합니다. 'b' 하나를 대문자(예: 'B')로 교체하면 문자 종류 조건과 반복 조건을 단 한 번의 변경으로 동시에 충족할 수 있습니다. 따라서 필요한 최소 변경 횟수는 1입니다.