[Programmers/Lv. 2/Python] 비밀 코드 해독

📎 문제 정보

난이도	Lv. 2 / 2025 프로그래머스 코드챌린지 1차 예선
유형	완전탐색, 조합
언어	Python
플랫폼 / 제목	Programmers / 비밀 코드 해독

---

🔍 문제 분석

• 1~n 사이 숫자 중 5개를 고른 비밀코드가 있고, q번의 힌트가 주어진다.
• 모든 힌트 조건을 동시에 만족하는 5개 조합의 경우의 수를 구한다.

---

💡 풀이 아이디어

• combinations(1..n, 5)로 후보 조합을 전부 생성한다.
• 각 후보에 대해 모든 쿼리를 순회하고 모든 쿼리를 통과한 후보만 카운트 한다.
• 내부 교집합 계산은 set 연산 case_set & query_set을 쓰면 정렬 순서에 무관하게 정확하다.

---

💻 코드

from itertools import combinations


def solution(n, q, ans):
    nums = [i for i in range(1, n + 1)]
    possible_cases = list(combinations(nums, 5))
    answer = 0

    for case in possible_cases:
        check = 0
        for i in range(len(q)):
            cnt = 0
            case_set = set(case)
            query_set = set(q[i])

            cnt += len(case_set & query_set)

            if cnt == ans[i]:
                check += 1

        if check == len(q):
            answer += 1

    return answer

 

---

⏱️ 시간/공간 복잡도

시간 복잡도	O(C(n,5) × len(q))
공간 복잡도	O(C(n,5))

---

📝 배운 점 / 실수했던 부분

• 내부 이중 루프에서 if x < y: break는 배열이 정렬되어 있다고 암묵적으로 가정해야한다.
• & 연산자로 교집합을 구하려면 양쪽 모두 set이어야 한다.
• list/tuple이 섞이면 .intersection()을 쓰자!!!