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

파이썬으로 K개의 서로 다른 문자를 포함하는 길이 N의 부분 문자열 찾기

프로그래밍 문제를 풀다 보면 K개의 서로 다른(고유한) 문자를 포함하는 크기 N의 부분 문자열을 찾거나 생성해야 하는 경우가 있습니다. 이럴 때 세 개의 매개변수를 받아 필요한 문자열을 반환하는 함수를 정의하고, 'if' 조건문을 활용하면 간단하게 해결할 수 있습니다.

예제 코드

다음은 해당 기능을 구현한 파이썬 코드 예시입니다.

def generate_my_string(string_size, substring_size, distinct_chars):
   my_string = ""
   count_1 = 0
   count_2 = 0

   for i in range(string_size):
      count_1 += 1
      count_2 += 1

      if (count_1 <= substring_size):
         if (count_2 <= distinct_chars):
            my_string = my_string + chr(96 + count_1)
         else:
            my_string = my_string + 'a'
      else:
         count_1 = 1
         count_2 = 1
         my_string = my_string + 'a'

   return my_string

my_string_size = 8
my_substring_size = 6
K_distinct_chars = 4

print("The string size is :")
print(my_string_size)
print("The substring size is :")
print(my_substring_size)
print("The distinct characters count is :")
print(K_distinct_chars)
print("The resultant string is :")
print(generate_my_string(my_string_size, my_substring_size, K_distinct_chars))

출력 결과

The string size is :
8
The substring size is :
6
The distinct characters count is :
4
The resultant string is :
abcdaaab

코드 동작 원리

  • 함수 정의: 'generate_my_string' 함수는 문자열 크기(string_size), 부분 문자열 크기(substring_size), 고유 문자 수(distinct_chars)를 매개변수로 받습니다.

  • 초기화: 결과를 담을 빈 문자열 my_string을 선언하고, 카운터 역할을 하는 두 개의 정수 변수(count_1, count_2)를 0으로 초기화합니다.

  • 반복 처리: for 반복문으로 문자열 크기만큼 순회하면서 두 카운터를 1씩 증가시킵니다.

  • 문자 생성: count_1이 부분 문자열 크기 이하이면서 count_2가 고유 문자 수 이하이면, chr(96 + count_1)을 사용해 알파벳 소문자(a, b, c, d...)를 차례대로 추가합니다.

  • 고유 문자 제한: count_2가 고유 문자 수를 초과하면 문자 'a'를 추가하여 서로 다른 문자의 종류를 K개로 제한합니다.

  • 패턴 초기화: count_1이 부분 문자열 크기를 초과하면 두 카운터를 1로 되돌리고 'a'를 추가해 패턴을 새로 시작합니다.

  • 반환: 완성된 문자열을 결과값으로 반환합니다.

  • 함수 호출: 함수 외부에서 문자열 크기(8), 부분 문자열 크기(6), 고유 문자 수(4)를 정의하고 콘솔에 출력한 뒤, 이 값들을 인자로 전달해 함수를 호출하고 결과를 화면에 표시합니다.

chr() 함수의 역할

ASCII 코드에서 97번은 소문자 'a'에 해당합니다. 따라서 chr(96 + count_1)은 count_1이 1일 때 'a', 2일 때 'b', 3일 때 'c'처럼 정수를 알파벳 소문자로 변환해 주는 핵심 역할을 합니다.

실행 결과 분석

위 예제에서 생성된 문자열은 "abcdaaab"입니다. 길이 8인 이 문자열에서 길이 6인 모든 부분 문자열("abcdaa", "bcdaaa", "cdaaab")을 살펴보면, 각각 정확히 4개(a, b, c, d)의 서로 다른 문자를 포함하고 있음을 확인할 수 있습니다. 이것이 바로 이 알고리즘이 달성하려는 목표이며, 카운터와 조건문만으로도 슬라이딩 윈도우 방식의 복잡한 구현 없이 원하는 패턴을 만들어낼 수 있음을 보여줍니다.