서로 다른 n개의 영어 알파벳으로 이루어진 배열이 있다고 가정해 보겠습니다. 여기에 값 k가 하나 더 주어지며, 우리는 k개의 서로 다른 인덱스(1부터 시작하는 인덱스)를 균등한 확률로 선택할 수 있습니다. 이 문제의 목표는 선택한 k개의 인덱스 중 적어도 하나에 문자 'a'가 포함될 확률을 구하는 것입니다.
문제 예시
예를 들어 letters = ['a', 'c', 'a', 'b', 'l', 'a', 'b', 'z']이고 k = 2라고 해보겠습니다. 이 경우 출력값은 64.28%가 됩니다. (1, 2), (1, 3)과 같은 형태의 조합이 총 28가지 존재하는데, 그중 (1, 2), (1, 3), (6, 7)처럼 'a'를 포함하는 조합은 18가지입니다. 따라서 확률은 18 / 28 = 0.6428, 즉 약 64.28%가 됩니다.
해결 접근 방법
이 문제는 다음 단계를 거쳐 해결할 수 있습니다.
- contain을 0으로 초기화합니다.
- total을 0으로 초기화합니다.
- letters에서 k개의 원소로 이루어진 모든 조합 c를 순회합니다.
- c에 "a"가 포함되어 있으면 contain을 1 증가시킵니다.
- 매 반복마다 total을 1 증가시킵니다.
- contain / total을 반환합니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
from itertools import combinations
def solve(letters, k):
contain = 0
total = 0
for c in combinations(letters, k):
if "a" in c:
contain += 1
total += 1
return contain / total
letters = ['a', 'c', 'a', 'b', 'l', 'a', 'b', 'z']
k = 2
print(solve(letters, k))입력
['a', 'c', 'a', 'b', 'l', 'a', 'b', 'z'], 2
출력
0.6428571428571429
itertools.combinations는 주어진 리스트에서 k개의 원소를 뽑는 모든 조합을 생성해 줍니다. 각 조합을 확인하며 'a'가 포함된 경우의 수와 전체 경우의 수를 세기만 하면, 원하는 확률을 손쉽게 계산할 수 있습니다.
다만 이 방식은 모든 조합을 직접 순회하므로, 조합의 개수가 기하급수적으로 늘어나는 큰 입력에서는 비효율적일 수 있습니다. 이런 경우에는 여사건을 활용하는 것이 좋습니다. 즉, 'a'가 하나도 포함되지 않을 확률을 먼저 구한 뒤 1에서 빼면 훨씬 빠르게 동일한 결과를 얻을 수 있습니다.