프로그래머스 | 배열 속 조건에 맞는 경우의 수 찾기

📌 문제

배열 nums: 길이가 100 이하, 인덱스 갯수 n개
배열 nums의 요소: a, b, 그리고 1 이상 10 이하의 정수
a와 b는 0 <= a < b < n
그리고 1 이상 10 이하의 정수 c가 있습니다.

배열 nums와 c가 입력될 때, nums[a] == nums[b] && nums[a]가 c로 나누어 떨어지는 경우의 수의 합을 출력하세요.

✨ 해결 방법

nums[a] == nums[b]인 경우와, nums[a]가 c로 나누어 떨어지는 경우를 차례대로 구합니다. 뒤의 조건은 nums[a] % c === 0의 코드를 사용하여 구현할 수 있습니다.

💻 solution 1

function solution(nums, c) {
    var answer = 0;

    for (let a = 0; a < nums.length -1; a++){
        for (let b = a+1; b < nums.length; b++){
            answer = (nums[a] === nums [b] && nums[a]%c === 0) ? answer+1 : answer;
            }
        }
    return answer;
}

우선 a가 나오고, b가 나와야 하기 때문에 a의 범위는 0번째부터 전체 길이의 -1까지, b의 범위는 a보다 1 큰 수부터 전체 길이 인덱스까지 검사합니다.
경우의 수의 합인 answer은 조건이 부합할 경우 1 증가하고, 아닐 경우 그대로 남습니다.

💻 solution 2

function solution(nums, c) {
    var answer = 0;
    var countMap = new Map();

    for (let num of nums) {
        // Map에 해당 숫자가 처음 등장하는 경우 1로 초기화, 그 외에는 현재 카운트에 1을 더함
        countMap.set(num, (countMap.get(num) || 0) + 1);
    }

    for (let count of countMap.values()) {
        // count가 2 이상이면서 c로 나누어 떨어지는 경우에만 조합 수를 계산
        if (count >= 2 && count % c === 0) {
            answer += (count * (count - 1)) / 2;
        }
    }

    return answer;
}

for 문의 중첩 사용은 시간 복잡도를 증가시켜 지양됩니다. 해당 프로그램은 Map을 사용하여 구현할 수도 있습니다.

nums 배열이 [4, 1, 2, 1, 4]일 때, countMap에는 각 숫자의 등장 횟수가 저장됩니다. 처음에는 빈 Map이 시작되고, 순서대로 각 숫자가 등장할 때마다 해당 숫자의 등장 횟수가 업데이트됩니다.

4가 등장하면 {4: 1}
1이 등장하면 {4: 1, 1: 1}
2가 등장하면 {4: 1, 1: 1, 2: 1}
1이 등장하면 {4: 1, 1: 2, 2: 1}
4가 등장하면 {4: 2, 1: 2, 2: 1}
따라서 countMap은 {4: 2, 1: 2, 2: 1}이 됩니다. 각 숫자가 키로, 해당 숫자의 등장 횟수가 값으로 저장됩니다.

answer += (count * (count - 1)) / 2; 의 공식은 nC2는 조합, 즉 n개의 원소에서 2개를 선택하는 경우의 수를 나타냅니다. nC2는 수학적으로 "n choose 2"로 읽으며, 다음과 같이 표현됩니다.
nC2= n! / 2!(n−2)! = n(n-1)/2

// 전개과정
n! = n(n-1)(n-2)...(3)(2)(1)
2! = 2(1)
(n-2)! = (n-2)(n-3)...(3)(2)(1)

nC2 =  {n(n−1)(n−2)...(3)(2)(1)} / {2(1)(n−2)(n−3)...(3)(2)(1)}

//공통항을 약분
nC2 = n(n-1)/2

두 가지 코드 모두 원하는 결과를 도출할 수 있지만, 성능과 코드의 간결함 측면에서는 솔루션 2를 추천합니다.