Skip to main content
동호의 블로그

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

•2 min•356 words

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

문제 설명

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

예제 입력/출력

nqansresult
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
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

제약 조건

  • 10 ≤ n ≤ 30
  • 1 ≤ m ≤ 10
    • q[i]의 길이 = 5
  • ans의 길이 = m
    • 0 ≤ ans[i] ≤ 5
  • 비밀 코드가 존재하지 않는 경우는 존재 X

문제 풀이

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

image.png

  • 비밀 코드는 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