출처 : 프로그래머스
난이도 : Level 2
문제 설명
당신은 비밀 조직의 보안 시스템을 뚫고 중요한 정보를 해독해야 합니다. 시스템은 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, 5, 7, 8, 9]
- [3, 5, 7, 8, 10]
정수 n, 입력한 정수를 담은 2차원 정수 배열 q와 시스템 응답을 담은 1차원 정수 배열 ans가 매개변수로 주어집니다. 이때, 비밀 코드로 가능한 정수 조합 개수를 return 하도록 solution 함수를 완성해 주세요.
제한사항
- 10 ≤ n ≤ 30
- 1 ≤ (q의 길이 = m) ≤ 10
- ans의 길이 = m
- 비밀 코드가 존재하지 않는(답이 0인) 경우는 주어지지 않습니다.
테스트 케이스 구성 안내
아래는 테스트 케이스 구성을 나타냅니다. 각 그룹 내의 테스트 케이스를 모두 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.
| 그룹 | 총점 | 추가 제한 사항 |
| #1 | 20% | m = 1 |
| #2 | 80% | 추가 제한 사항 없음 |
입출력 예
| n | q | ans | result |
| 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 |
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
비밀 코드로 가능한 정수 조합은 아래와 같이 5개가 있습니다.
- [1, 2, 3, 5, 8]
- [1, 3, 5, 8, 12]
- [2, 4, 5, 8, 12]
- [2, 5, 8, 9, 10]
- [5, 8, 9, 10, 12]
따라서 5를 return 해야 합니다.
----------------------------------------------------------------------------------------------------------------------------
문제 해독
1에서 N까지의 숫자중 5가지의 수로 조합가능한 비밀 코드를 생성하여 m번 동안 시도한 결과에 대해 각각 입력한 비밀 코드에서 시스템 응답의 수와 동일한 결과를 출력할 수 있는 비밀 코드의 경우의 수를 계산하는 문제입니다. (m이 5일 경우 5개의 비밀코드와 응답 결과에 대해 동일하게 출력이 가능한 비밀 코드의 개수)
문제접근
1 ~ N까지 조합가능한 모든 비밀코드를 생성하여 각각의 입력코드와 시스템 응답수가 모두 일치하는 비밀코드의 개수를 구합니다.
필요 변수 리스트
- List<int[]> allcombines(1~N까지 모든 경우의 비밀코드가 담긴 변수)
필요 알고리즘
- 완전탐색
- 백트래킹
using System;
using System.Collections.Generic;
public class Solution {
public int solution(int n, int[,] q, int[] ans) {
int answer = 0;
// 모든 입력가능한 비밀코드
List<int[]> allCombinations = new List<int[]>();
GetAllCombination(1, n, new List<int>(), allCombinations);
// 비밀코드별 Invaild 검사
foreach(int[] combination in allCombinations)
{
// 탐색용 codeSet
HashSet<int> codeSet = new HashSet<int>(combination);
bool isClear = true;
for(int i = 0; i < ans.Length; i++)
{
int compareCount = 0;
for(int j = 0; j < 5; j++)
{
// 비밀코드의 값에 입력값이 있는지 확인
if(codeSet.Contains(q[i,j]))
compareCount++;
}
// 비밀코드의 같은 개수가 응답 개수와 같는지 확인
if(compareCount != ans[i])
{
isClear = false;
break;
}
}
if(isClear)
answer++;
}
return answer;
}
// 모든 경우의 비밀코드 탐색용
private void GetAllCombination(int start, int n, List<int> current, List<int[]> result)
{
if(current.Count == 5)
{
result.Add(current.ToArray());
return;
}
for(int i = start; i <= n; i++)
{
current.Add(i);
GetAllCombination(i + 1, n, current, result);
current.RemoveAt(current.Count - 1); // 백트래킹
}
}
}
