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

문제 출처

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

프로그래머스

문제 설명

당신은 비밀 조직의 보안 시스템을 뚫고 중요한 정보를 해독해야 합니다. 시스템은 1부터 n까지의 서로 다른 정수 5개가 오름차순으로 정렬된 비밀 코드를 가지고 있으며, 당신은 이 비밀 코드를 맞혀야 합니다.

당신은 비밀 코드를 알아내기 위해 암호 분석 도구를 사용하며, m번의 시도를 할 수 있습니다. 각 시도마다 서로 다른 5개의 정수를 입력하면, 시스템은 그 중 몇 개가 비밀 코드에 포함되어 있는지 알려줍니다.

• 만약 비밀 코드가 [3, 5, 7, 9, 10]이고, 입력한 정수가 [1, 2, 3, 4, 5]라면 비밀 코드에 포함된 정수는 3, 5 두 개이므로 시스템은 2를 응답합니다.

당신은 m번의 시도 후, 비밀 코드로 가능한 정수 조합의 개수를 알고 싶습니다.

비밀 코드에 사용된 정수의 범위가 1~10일 때, 아래와 같이 5번의 시도를 했다고 가정해 보겠습니다.

비밀 코드로 가능한 정수 조합은 아래와 같이 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 함수를 완성해 주세요.

---

제한사항

• 10 ≤ n ≤ 30
• 1 ≤ (q의 길이 = m) ≤ 10
  • q[i]의 길이 = 5
  • q[i]는 i+1번째 시도에서 입력한 5개의 서로 다른 정수를 담고 있으며, 오름차순으로 정렬되어 있습니다.
  • 1 ≤ q[i][j] ≤ n
• ans의 길이 = m
  • ans[i]는 i+1번째 시도에서 입력한 5개의 정수 중 비밀 코드에 포함된 정수의 개수를 나타냅니다.
  • 0 ≤ ans[i] ≤ 5
• 비밀 코드가 존재하지 않는(답이 0인) 경우는 주어지지 않습니다.

---

테스트 케이스 구성 안내

아래는 테스트 케이스 구성을 나타냅니다. 각 그룹 내의 테스트 케이스를 모두 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.

입출력 예 #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 해야 합니다.

풀이 방법

• 브루트포스를 활용하여 구현하였다. 
  • 숫자가 오름차순으로 정렬되어 있으므로, n을 1~5 조합부터 시작하여 n-4 ~ n의 조합까지 순차적으로 조합하며 가능한 방법을 찾는다.

• 해당 문자열이 사진과 같이 되어있을때, q[i]를 순회하여 공통의 숫자(common)갯수를 찾아내고, 이를 ans와 비교하며 맞으면 넘어가고, 아니면 break를 통해 바로 탈출 시킨다.

풀이 코드

function solution(n, q, ans) {
    let answer = 0;
    
    //5중 반복문을 통해, 계속 값을 비교해본다.
    for(let a = 1; a <= n - 4; a++){
        for(let b = a + 1; b <= n - 3; b++){
            for(let c = b + 1; c <= n - 2; c++){
                for(let d = c + 1; d <= n - 1; d++){
                    for(let e = d + 1; e <= n; e++){
                        let arr = [a, b, c, d, e];
                        let isValid = true;
                        for(let i = 0; i < q.length; i++){
                            let common = 0;
                            //num과 qNum을 순환하며, 비교, 같은것이 나오면 다음 숫자로 전환
                            for(const num of arr){
                                for(const qNum of q[i]){
                                    if(num == qNum){
                                        common++;
                                        break;
                                    }
                                };
                            };
                            
                            if(common !== ans[i]){
                                isValid = false;
                                break;
                            }
                        }
                        
                        if(isValid){
                            answer++;
                        }
                    }
                }
            }
        }
    }
    
    return answer;
}

결과

회고

• n이 커지면 다른 방법을 써야할듯 함