코딩테스트는 현실적인 문제를 해결하는 능력을 평가하기 위한 중요한 요소입니다. 이번 강좌에서는 ‘칵테일 만들기’라는 주제로 알고리즘 문제를 다루고, 이를 해결하기 위해 필요한 개념과 방법론을 상세하고 체계적으로 설명합니다.
문제 설명
당신은 한 바의 바텐더로서 다양한 재료를 사용하여 여러 가지 칵테일을 만들 수 있습니다. 각 칵테일마다 필요로 하는 재료가 다릅니다. 당신의 임무는 주어진 재료를 바탕으로 각각의 칵테일을 만들어낼 수 있는지를 판단하는 프로그램을 작성하는 것입니다.
문제 정의
주어진 재료 리스트와 칵테일 리스트가 있을 때, 각 칵테일을 만들기 위한 재료가 주어진 리스트에 포함되어 있는지 확인하세요.
입력
- 리스트 A: 사용 가능한 재료 (문자열 배열)
- 리스트 B: 만들고 싶은 칵테일 (문자열 배열, 각 칵테일에는 필요한 재료가 열거됨)
출력
각 칵테일을 만들 수 있는지 여부를 true 또는 false로 출력하는 배열을 반환하세요.
예시
입력: A = ["진", "퍼프", "레몬", "소다"] B = ["진 토닉", "퍼프 음료", "모히토"] 출력: [true, true, false]
문제 풀이 과정
이 문제를 풀기 위해서는 다음 단계로 접근할 수 있습니다.
1. 데이터 구조 선택
먼저, 사용 가능한 재료가 들어있는 리스트 A를 Set 구조로 변환해주면 좋습니다. Set은 중복을 허용하지 않으며, 요소의 존재 여부를 O(1)의 시간 복잡도로 확인할 수 있습니다. 이를 통해 재료의 포함 여부를 빠르게 확인할 수 있습니다.
2. 칵테일 재료 확인
각 칵테일을 만들기 위해 필요한 재료를 체크할 때, 각 칵테일 문자열을 공백으로 분리하여 재료 리스트를 얻고, 이 리스트의 모든 재료가 A에 포함되어 있는지 판별해야 합니다. 이 과정을 반복하여 모든 칵테일에 대해 확인을 진행합니다.
3. 구현
이제 이를 자바로 구현해 보겠습니다. 아래는 전체 코드입니다:
import java.util.HashSet;
import java.util.Set;
public class CocktailMaker {
public static boolean[] canMakeCocktails(String[] availableIngredients, String[] cocktails) {
// Set에 사용 가능한 재료 추가
Set<String> ingredientsSet = new HashSet<>();
for (String ingredient : availableIngredients) {
ingredientsSet.add(ingredient);
}
boolean[] results = new boolean[cocktails.length];
// 칵테일별로 재료 확인
for (int i = 0; i < cocktails.length; i++) {
String[] requiredIngredients = cocktails[i].split(" ");
boolean canMake = true;
for (String ingredient : requiredIngredients) {
if (!ingredientsSet.contains(ingredient)) {
canMake = false;
break;
}
}
results[i] = canMake;
}
return results;
}
public static void main(String[] args) {
String[] A = {"진", "퍼프", "레몬", "소다"};
String[] B = {"진 토닉", "퍼프 음료", "모히토"};
boolean[] result = canMakeCocktails(A, B);
for (boolean res : result) {
System.out.print(res + " ");
}
}
}
4. 성능 평가
이 알고리즘의 시간 복잡도는 다음과 같습니다:
- 재료를
Set에 추가하는 과정:O(m)(m은 A의 길이) - 각 칵테일의 재료를 확인하는 과정:
O(n * k)(n은 B의 길이, k는 각 칵테일의 평균 재료 개수)
따라서 전체 시간 복잡도는 O(m + n * k)로, 충분히 효율적입니다.
결론
이와 같은 방식으로 칵테일을 만들 수 있는지 여부를 판단하는 프로그램을 작성할 수 있습니다. 코딩테스트에서는 이와 같은 문제에 대해 철저하게 분석하고, 최적의 솔루션을 찾는 과정이 중요합니다. 문제를 잘 이해하고, 단계적으로 접근하여 구현하는 연습이 필요합니다. 다양한 접근 방법과 최적화 전략을 배워보세요.