APCS Jun 2024 - o078 Q3 [Python]

문제 설명:

K개의 문자로 이루어진 집합과 문자열 S가 주어집니다. 이 문자 집합으로 만들 수 있는 길이 L의 문자열 중 S의 부분 문자열이 아니면서 사전순으로 가장 작은 문자열을 구하세요. 예를 들어 {a, c, m}으로 만들 수 있는 길이 2의 문자열은 aa < ac < am < ca < cc < cm < ma < mc < mm 순서입니다. S가 accaamcm이면 포함되지 않는 가장 작은 문자열은 ma입니다.

def generate_strings(letters, length, current_string, all_strings):
    if length == 0:
        all_strings.append(current_string)
        return
    for letter in letters:
        generate_strings(letters, length - 1, current_string + letter, all_strings)

letters = list(input())
L = int(input())
S = input()

all_strings = []
generate_strings(letters, L, "", all_strings)

for string in all_strings:
    if string not in S:
        print(string)
        break

---

풀이 보고서

1. 재귀

   def generate_strings(letters, length, current_string, all_strings):
   if length == 0:
       all_strings.append(current_string)
       return
   for letter in letters:
       generate_strings(letters, length - 1, current_string + letter, all_strings)
   

   주어진 문자로 지정한 길이의 모든 문자열을 생성하는 재귀 함수입니다. letters = ['a', 'b'], length = 2라면:

   1. 처음에는 generate_strings(['a', 'b'], 2, "", all_strings)를 호출합니다. length가 0이 아니므로 반복문에 들어가 첫 문자 'a'를 선택하고 generate_strings(['a', 'b'], 1, "a", all_strings)를 호출합니다.
   2. 두 번째 호출에서도 length가 0이 아니므로 다시 'a'를 선택하고 generate_strings(['a', 'b'], 0, "aa", all_strings)를 호출합니다.
   3. 세 번째 호출에서는 length가 0이므로 "aa"를 all_strings에 추가하고 이전 단계로 돌아갑니다.
   4. 두 번째 호출로 돌아와 다음 문자 'b'로 generate_strings(['a', 'b'], 0, "ab", all_strings)를 호출합니다.
   5. 네 번째 호출에서도 length가 0이므로 "ab"를 추가하고 돌아갑니다.

   이 과정을 반복하면 "aa", "ab", "ba", "bb"가 순서대로 all_strings에 추가됩니다.

핵심 개념:

• 재귀

---

• [✔️] 필요하면 코드를 그대로 사용해도 됩니다.
• [✔️] 공유할 때 출처를 표시해 주세요.
• [✔️] 이 글의 풀이 보고서는 AI와 협업해 작성했습니다. 오류가 있으면 알려 주세요.

---

사실 더 빠르게 할 수도 있습니다

def generate_strings(letters, length, current_string, existing_strings):
    if length == 0:
        if current_string not in existing_strings:
            print(current_string)
            return True
        return False
    for letter in letters:
        if generate_strings(letters, length - 1, current_string + letter, existing_strings):
            return True
    return False

letters = list(input())
L = int(input())
S = input()

# 使用Set來提升查找效率
existing_strings = set(S[i:i+L] for i in range(len(S) - L + 1))

generate_strings(letters, L, "", existing_strings)

• 설명 실력이 부족해서 나머지는 직접 이해해 주세요 :).

이 글은 번체 중국어 원문을 AI로 번역했습니다. 의미나 표현에 차이가 있을 수 있으니 정확한 내용은 번체 중국어 원문을 기준으로 확인해 주세요.