자바스크립트 코딩테스트 강좌, 칵테일 만들기

이 강좌에서는 자바스크립트를 이용한 코딩테스트 문제를 다룹니다.
특히 칵테일 만들기라는 주제를 가지고 다양한 알고리즘 문제를
해결해 보겠습니다. 오늘 다룰 문제는 “서브셋의 조합으로 칵테일 만들기”입니다.

문제 설명

주어진 재료들을 이용하여 가능한 모든 칵테일의 조합을 찾아야 합니다.
각 칵테일은 두 가지 이상의 재료로 이루어져야 하며, 재료의 조합을
중복 없이 나타내야 합니다.

입력

재료의 수 N (1 ≤ N ≤ 20)
각 재료의 이름이 포함된 문자열 배열 ingredients

출력

가능한 모든 칵테일 조합의 배열을 반환해야 합니다. 각 조합은
["재료1", "재료2", ...] 형태로 나타내어야 하며,
각 조합에서 재료들은 알파벳 순서로 정렬되어 있어야 합니다.

예제

입력

const ingredients = ["vodka", "orange juice", "grenadine"];

출력

[["grenadine", "orange juice"], ["grenadine", "vodka"], ["orange juice", "vodka"], ["grenadine", "orange juice", "vodka"]]

문제 해결 과정

이 문제를 해결하기 위해 우리는 먼저 모든 가능한 조합을 만드는
방법을 생각해보아야 합니다. 재귀함수나 비트를 이용한 조합 생성을
통해 문제를 해결할 수 있습니다.

알고리즘 설계

칵테일의 조합을 생성하기 위해 재귀적인 접근 방식을 사용합니다.
알고리즘의 주된 단계는 다음과 같습니다:

재료 배열을 정렬합니다. (출력 결과를 정렬된 형태로 만들기 위함)
재귀함수를 사용하여 재료의 조합을 생성합니다.
조합이 두 개 이상의 재료로 이루어진 경우 결과 배열에 추가합니다.

코드 구현

이제 우리가 설계한 알고리즘을 자바스크립트로 구현해보겠습니다.

function cocktailCombinations(ingredients) {
    const result = [];
    
    ingredients.sort();

    const generateCombinations = (start, currentCombination) => {
        if (currentCombination.length > 1) {
            result.push([...currentCombination]);
        }

        for (let i = start; i < ingredients.length; i++) {
            currentCombination.push(ingredients[i]);
            generateCombinations(i + 1, currentCombination);
            currentCombination.pop();
        }
    };

    generateCombinations(0, []);

    return result;
}

// 사용 예시
const ingredients = ["vodka", "orange juice", "grenadine"];
console.log(cocktailCombinations(ingredients));

코드 설명

위의 cocktailCombinations 함수는 재료 배열을 입력받아
가능한 모든 칵테일 조합을 생성합니다. 내부에서 generateCombinations라는
재귀함수를 정의하고 호출하여 조합을 생성합니다.

상세 기능

재료 정렬: 입력된 재료를 정렬하여 결과의 일관성을 유지합니다.
재귀 호출: 재귀 함수를 통해 각 재료를 선택하고, 조합 가능성을 탐색합니다.
조합 추가: 현재 조합의 길이가 2 이상일 경우에만 결과에 추가합니다.

복잡도 분석

이 알고리즘의 시간 복잡도는
O(2^N)입니다.
이는 각 재료에 대해 선택할지 말지를 결정하는 이진 선택 문제로,
모든 조합을 탐색할 때 물리적으로 가능한 최대 조합의 수와
동일하기 때문입니다. 공간 복잡도는 배열의 깊이에 비례하며,
최악의 경우 사용되는 추가 메모리는 조합의 수에 따라 달라집니다.

테스트 케이스

다양한 입력에 대해 함수를 테스트하여 정확성을 검증해보겠습니다.

// 테스트 케이스
const test1 = ["gin", "tonic", "lime"];
const test2 = ["whiskey", "soda", "angostura", "lemon"];
const test3 = [];

// 결과 출력
console.log(cocktailCombinations(test1)); // [["gin", "lime"], ...]
console.log(cocktailCombinations(test2)); // ...
console.log(cocktailCombinations(test3)); // []

결론

이 강좌에서는 자바스크립트를 이용한 칵테일 조합 문제를 해결하는
과정을 함께 해보았습니다. 배열, 재귀, 조합 가능성에 대한
깊은 이해를 통해 우리는 코딩테스트에서 흔히 접할 수 있는
문제 유형에 대한 대응 전략을 더욱 효과적으로
익힐 수 있었습니다.

부가적인 정보

실제 코딩테스트에서는 종종 예외 처리나 입력 제약 조건이 추가될 수 있습니다.
이러한 조건들을 반영하여 코드를 더 발전시키는 것도 좋은 연습이 될 것입니다.
각자의 상황에 맞춰 다양한 기능을 추가해 나가는 과정이 중요한 만큼,
이번 문제를 통해 더 나아갈 기회를 만들어가시길 바랍니다.