프로그래머스

프로그래머스 비밀 코드 해독 풀이: 조합 완전탐색과 교집합

작성자: solve together · 작성 언어: Python

0. 문제 링크와 출처

  • 문제: 비밀 코드 해독
  • 출처: 프로그래머스, 2025 프로그래머스 코드챌린지 1차 예선
  • 자체 판단 난이도: Level 2

비밀 코드가 오름차순 5개 숫자의 조합이라는 조건을 그대로 활용해 후보를 만들고, 모든 시도의 응답과 일치하는 후보만 세면 됩니다. 조합 수가 제한 안에서 충분히 작지만 검증 조건이 여러 개이므로 Level 2로 판단했습니다.

문제 원문과 제한 조건은 변경될 수 있으므로 제출 전에는 공식 문제 페이지를 다시 확인하세요.

1. 문제 요약

1부터 n까지의 서로 다른 정수 중 5개가 비밀 코드입니다. 도구를 사용한 각 시도 q[i]에는 서로 다른 숫자 5개가 들어 있고, ans[i]는 해당 시도와 비밀 코드가 공유하는 숫자의 개수입니다.

가능한 5개 조합을 하나씩 만들면서 모든 시도에 대해 다음 조건을 확인합니다.

len(비밀 코드 후보 ∩ q[i]) == ans[i]

모든 조건을 통과한 후보의 개수를 반환합니다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

핵심 관찰

비밀 코드의 순서는 중요하지 않고 숫자 5개의 선택만 중요합니다. 따라서 순열이 아니라 조합만 생성해야 합니다. n ≤ 30이므로 후보 수는 최대 C(30, 5) = 142,506개이며, 각 후보를 최대 10개의 시도와 비교해도 충분히 확인할 수 있습니다.

각 시도는 숫자가 5개뿐이므로 후보와 시도의 교집합 크기를 집합 연산으로 계산하면 중복 숫자를 잘못 세는 일을 피할 수 있습니다. 하나의 시도라도 응답과 다르면 즉시 다음 후보로 넘어가 불필요한 비교를 줄입니다.

3. 문제 해결 코드 (Python)

from itertools import combinations


def solution(n, q, ans):
    query_sets = [set(query) for query in q]
    answer = 0

    for candidate in combinations(range(1, n + 1), 5):
        candidate_set = set(candidate)

        if all(len(candidate_set & query) == expected
               for query, expected in zip(query_sets, ans)):
            answer += 1

    return answer

후보 조합 수를 C(n, 5), 시도 횟수를 m이라고 하면 각 후보와 모든 시도를 비교하는 시간 복잡도는 O(C(n, 5) × m)입니다. 집합 변환과 후보 집합에 사용하는 추가 공간은 O(5m + 5), 문제 조건에서는 O(m)으로 볼 수 있습니다.

4. 오답 접근과 반례

시도 배열의 숫자를 위치별로 비교하면 틀립니다. 비밀 코드와 시도는 모두 오름차순이지만 일치 여부는 같은 위치가 아니라 숫자의 포함 여부로 결정됩니다. 비밀 코드가 [3, 5, 7, 9, 10]이고 시도가 [1, 2, 3, 4, 5]라면 위치가 같은 숫자는 없어도 공통 숫자 3과 5가 있으므로 응답은 2입니다.

또한 시도 하나의 조건만 만족하는 후보를 바로 세면 안 됩니다. 예를 들어 두 시도의 응답이 각각 [1, 0]인데 첫 번째 시도만 확인하면, 두 번째 시도에 포함된 숫자를 가진 잘못된 후보도 답에 포함될 수 있습니다. 모든 시도를 통과한 후보만 세어야 합니다.

5. 공식 예제와 추가 검증

공식 예제 2개를 Python 3.12.4에서 실행했고 모두 기대값과 일치했습니다.

예제 기대 출력 확인 결과
1 3 통과
2 5 통과

추가 검증 1: 한 번의 시도에서 모두 불일치

입력: n=10, q=[[1, 2, 3, 4, 5]], ans=[0]
기대 출력: 1
확인 결과: 통과
검증 목적: 6부터 10까지의 유일한 조합만 남는지 확인

추가 검증 2: 한 번의 시도와 완전히 일치

입력: n=10, q=[[1, 2, 3, 4, 5]], ans=[5]
기대 출력: 1
확인 결과: 통과
검증 목적: 시도 조합 자체만 후보가 되는 경계 확인

추가 검증 3: 조건을 여러 번 교차 확인

입력: n=10, q=[[1, 2, 3, 4, 5], [2, 3, 4, 5, 6]], ans=[2, 3]
기대 출력: 36
확인 결과: 통과
검증 목적: 두 시도의 교집합 조건을 동시에 적용하는지 확인

6. 다른 풀이 방식 검색 및 비교

공개된 풀이들도 조합 완전탐색을 사용합니다. 이 글에서는 시도 배열을 미리 집합으로 변환하고 후보도 집합으로 바꿔 교집합 크기를 비교했습니다. 숫자 5개라는 고정 크기를 이용해 문제의 조건을 코드에 직접 대응시킨 방식입니다.

마무리

이 문제는 제한 조건을 보고 복잡한 추론보다 모든 후보를 확인하는 것이 더 안전한 경우입니다. n = 30에서도 5개 조합의 수가 감당 가능한 범위이므로, 조합을 생성하고 각 시도의 교집합 조건을 모두 통과하는지 확인하면 간결하게 해결할 수 있습니다.

#완전탐색#프로그래머스#난이도 2