[programmers] Lv.2 비밀 코드 해독 (python)

✏️ 문제

당신은 비밀 조직의 보안 시스템을 뚫고 중요한 정보를 해독해야 합니다.
시스템은 1부터 n까지의 서로 다른 정수 5개가 오름차순으로 정렬된 비밀 코드를 가지고 있으며, 당신은 이 비밀 코드를 맞혀야 합니다.당신은 비밀 코드를 알아내기 위해 암호 분석 도구를 사용하며, m번의 시도를 할 수 있습니다. 각 시도마다 서로 다른 5개의 정수를 입력하면, 시스템은 그 중 몇 개가 비밀 코드에 포함되어 있는지 알려줍니다.
만약 비밀 코드가 [3, 5, 7, 9, 10]이고, 입력한 정수가 [1, 2, 3, 4, 5]라면 비밀 코드에 포함된 정수는 3, 5 두 개이므로 시스템은 2를 응답합니다.당신은 m번의 시도 후, 비밀 코드로 가능한 정수 조합의 개수를 알고 싶습니다.
비밀 코드에 사용된 정수의 범위가 1~10일 때, 아래와 같이 5번의 시도를 했다고 가정해 보겠습니다.

입력한 정수 | 시스템 응답(일치하는 개수)
[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개가 있습니다.
[3, 4, 7, 9, 10]
첫 번째 시도에서 비밀 코드에 포함된 정수가 3, 4로 2개 있습니다.
두 번째 시도에서 비밀 코드에 포함된 정수가 7, 9, 10으로 3개 있습니다.
세 번째 시도에서 비밀 코드에 포함된 정수가 3, 7, 9, 10으로 4개 있습니다.
네 번째 시도에서 비밀 코드에 포함된 정수가 7, 9, 10으로 3개 있습니다.
다섯 번째 시도에서 비밀 코드에 포함된 정수가 3, 4, 7로 3개 있습니다.

[3, 5, 7, 8, 9]
첫 번째 시도에서 비밀 코드에 포함된 정수가 3, 5로 2개 있습니다.
두 번째 시도에서 비밀 코드에 포함된 정수가 7, 8, 9로 3개 있습니다.
세 번째 시도에서 비밀 코드에 포함된 정수가 3, 7, 8, 9로 4개 있습니다.
네 번째 시도에서 비밀 코드에 포함된 정수가 5, 7, 9로 3개 있습니다.
다섯 번째 시도에서 비밀 코드에 포함된 정수가 3, 5, 7로 3개 있습니다.

[3, 5, 7, 8, 10]
첫 번째 시도에서 비밀 코드에 포함된 정수가 3, 5로 2개 있습니다.
두 번째 시도에서 비밀 코드에 포함된 정수가 7, 8, 10으로 3개 있습니다.
세 번째 시도에서 비밀 코드에 포함된 정수가 3, 7, 8, 10으로 4개 있습니다.
네 번째 시도에서 비밀 코드에 포함된 정수가 5, 7, 10으로 3개 있습니다.
다섯 번째 시도에서 비밀 코드에 포함된 정수가 3, 5, 7로 3개 있습니다.

정수 n, 입력한 정수를 담은 2차원 정수 배열 q와 시스템 응답을 담은 1차원 정수 배열 ans가 매개변수로 주어집니다. 
이때, 비밀 코드로 가능한 정수 조합 개수를 return 하도록 solution 함수를 완성해 주세요.

 

🔢 알고리즘

 

#조합  #완전탐색

 

 

🤯 풀이 방법

 

가능한 경우의 조합을 모두 만들고,

각 시도마다 입력한 조합과 일치하는 수의 개수를 찾는다. 각각을 set으로 만들어 intersection 을 사용한다.

전체 시도했을 때 모두 일치했으면 가능한 암호 조합에 해당한다.

 

👾 구현 코드 (파이썬)

import itertools

def solution(n, q, ans):
    answer = 0
    m = len(ans)  # 시도한 횟수
    nums = [x for x in range(1, n + 1)]
    
    comb = itertools.combinations(nums, 5)  # 각각의 타입은 튜플
    
    for c in comb:  # 조합 하나씩 탐색
        cnt = 0
        for i in range(m):
            if len(set(c).intersection(set(q[i]))) == ans[i]:   # 교집합의 수 확인해서 ans의 값과 일치하는지 확인
                cnt += 1
            else:
                break
        if cnt == m:    # 모두 일치하는 경우 가능한 정수 조합으로 판단
            answer += 1

    return answer

 

 

🤖 GPT의 개선 제안

 

1. 불필요한 set(q[i]) 매번 생성 제거

q[i]는 이미 리스트이므로, 이를 미리 set으로 바꿔서 저장하면 반복적으로 set()을 생성하는 비용을 줄일 수 있습니다.

q_sets = [set(query) for query in q]

 

 

2. 조기 종료 개선

현재 cnt를 세고 cnt == m으로 판단하지만, break가 발생하면 이미 실패이므로 else 없이 바로 continue나 pass로 로직을 간단하게 만들 수 있습니다.

 

3. 리팩토링 (가독성 향상)

 

all()을 활용하면 더 파이썬다운 방식으로 표현할 수 있습니다.

 if all(len(comb_set & q_sets[i]) == ans[i] for i in range(len(ans))):
            valid_count += 1