[programmers/python] 비밀 코드의 가능한 조합 개수 구하기

문제 정리

- url : https://school.programmers.co.kr/learn/courses/30/lessons/388352

1. 비밀 코드: 1부터 n까지의 수 중 5개의 서로 다른 정수로 이루어진다.
2. 시도 데이터: m개의 시도가 주어지고, 각 시도마다 5개의 정수를 입력하면 시스템은 그 중 몇 개가 비밀 코드에 포함되는지 알려준다.
3. 목표: 주어진 시도 데이터와 시스템의 응답을 모두 만족하는 비밀 코드 조합의 개수를 구하는 것이다.

---

예시로 살펴보기

예를 들어, n=10일 때의 시도 데이터는 아래와 같다.

입력한 정수	시스템 응답 (일치 개수)
[1, 2, 3, 4, 5]	2
[6, 7, 8, 9, 10]	3
[3, 7, 8, 9, 10]	4
[2, 5, 7, 9, 10]	3
[3, 4, 5, 6, 7]	3

이 경우, 문제에서 가능한 비밀 코드 조합이 3개라고 알려준다. 우리는 이를 프로그램으로 일반화하여 구해야 한다.

---

문제 해결 흐름

1. 비밀 코드 후보 생성
   비밀 코드는 반드시 5개의 정수로 이루어져야 한다. 따라서 1부터 n까지의 정수 중 5개를 고른 모든 조합을 생성한다.
2. 후보 코드 검증
   각 후보 코드에 대해 주어진 모든 시도 데이터를 검사한다. 각 시도에서 입력한 정수와 후보 코드의 교집합 크기가 시스템 응답과 정확히 일치해야 한다.
3. 조건을 만족하는 코드 개수 세기
   검증을 통과한 후보 코드만 비밀 코드로 인정된다. 이 개수를 세면 된다.

---

최종 코드

아래는 이를 파이썬으로 구현한 최종 풀이 코드이다.

from itertools import combinations

def solution(n, qlist, ans):
    # 1. 가능한 비밀 코드 후보: 1~n 중 5개의 조합
    possible_codes = list(combinations(range(1, n + 1), 5))
    
    answer = 0
    
    # 2. 각 후보 코드 검증
    for code in possible_codes:
        valid = True
        for q, a in zip(qlist, ans):
            # 입력한 정수(q)와 후보 코드의 교집합 개수
            cnt = len(set(code) & set(q))
            if cnt != a:
                valid = False
                break
        if valid:
            answer += 1
    
    return answer

---

주요 아이디어

✅ 비밀 코드는 항상 5개의 정수로 이루어진다
itertools.combinations(range(1, n+1), 5)를 사용해 가능한 모든 경우의 수를 구하면 된다.

✅ 교집합 크기를 통해 응답과 비교한다
입력한 정수 집합과 후보 코드 집합의 교집합 크기를 구해 시스템 응답과 비교한다.

✅ 조건이 불일치하면 즉시 중단한다
조건이 불일치하는 경우는 바로 다음 후보를 검증하도록 하여 불필요한 계산을 줄인다.

---

정답 검증

아래 예시로 결과를 확인할 수 있다.

print(solution(10, [[1, 2, 3, 4, 5],
                     [6, 7, 8, 9, 10],
                     [3, 7, 8, 9, 10],
                     [2, 5, 7, 9, 10],
                     [3, 4, 5, 6, 7]], [2, 3, 4, 3, 3]))  # 출력: 3

print(solution(15, [[2, 3, 9, 12, 13],
                     [1, 4, 6, 7, 9],
                     [1, 2, 8, 10, 12],
                     [6, 7, 11, 13, 15],
                     [1, 4, 10, 11, 14]], [2, 1, 3, 0, 1]))  # 출력: 5