[프로그래머스] 비밀 코드 해독

문제 설명

• 암호 분석 도구를 사용하여 비밀 코드로 가능한 정수 조합 개수를 구하는 문제

예제 입력/출력

제약 조건

• 10 ≤ n ≤ 30

• 1 ≤ m ≤ 10
• q[i]의 길이 = 5

• ans의 길이 = m
• 0 ≤ ans[i] ≤ 5

• 비밀 코드가 존재하지 않는 경우는 존재 X

문제 풀이

1️⃣ 비밀 코드와 암호 분석 도구

• 비밀 코드는 1 ~ n까지의 서로 다른 정수 5개가 오름차순으로 정렬된 값이다.

• 비밀 코드를 알아내기 위해 암호 분석 도구를 m번 사용할 수 있다.
• 각 시도마다 서로 다른 5개의 정수를 입력하면, 시스템은 그 중 몇 개가 비밀 코드에 포함되는지 알려준다.

2️⃣ 비밀 코드로 가능한 정수 조합 구하기

• 비밀 코드는 1 ~ n 중 서로 다른 정수 5개를 고른 조합이며, 순서는 의미가 없고 항상 오름차순으로 정렬되어 있다고 볼 수 있다.

• 즉, 비밀 코드의 후보는 C(n, 5)개의 모든 조합 중 하나다.

• 어떤 조합이 실제 비밀 코드 후보가 되려면, 모든 Query에 대해 겹치는 개수가 정확히 ans[i]와 같아야 한다.

3️⃣ 브루트포스

• 검증 방식은 다음과 같다.
1. 1 ~ n에서 5개를 뽑는 모든 조합을 생성한다.
2. 각 후보에 대해 모든 Query를 검사한다.
• Query 배열과 후보 조합 사이의 교집합 크기를 계산
• 하나라도 ans[i]와 다르다면 즉시 검사를 종료
3. 모든 Query를 통과한 조합만 카운트한다.

def solution(n, queries, answers):
    possible_count = 0
    
    # 가능한 모든 비밀 코드 후보
    for secret_code in combinations(range(1, n + 1), 5):
        valid = True
        
        for i, query in enumerate(queries):
            if count_overlap(secret_code, query) != answers[i]:
                valid = False
                break
        
        if valid:
            possible_count += 1
    
    return possible_count

4️⃣ 교집합 개수 계산

• 후보 조합과 Query는 모두 길이가 5이므로 이중 반복문으로 단순 비교했다.
• 겹치는 원소 개수 = secret 중 query에 포함된 원소 수

def count_overlap(secret, query):
    overlap_count = 0
    for num in secret:
        if num in query:
            overlap_count += 1
    return overlap_count

5️⃣ 시간 복잡도 분석

• 전체 조합 수는 C(n, 5)
• n ≤ 30 이라면 최대 142506개

• 각 조합마다 m개의 Query 계산

• 각 검사는 길이 5

• 충분히 제한 시간 내에 해결 가능하다고 판단했다.

풀이 코드

from itertools import combinations

def count_overlap(secret, query):
    overlap_count = 0
    for num in secret:
        if num in query:
            overlap_count += 1
    return overlap_count

def solution(n, queries, answers):
    possible_count = 0
    
    # 가능한 모든 비밀 코드 후보
    for secret_code in combinations(range(1, n + 1), 5):
        valid = True
        
        for i, query in enumerate(queries):
            if count_overlap(secret_code, query) != answers[i]:
                valid = False
                break
        
        if valid:
            possible_count += 1
    
    return possible_count