안녕하세요! 이번 블로그 글에서는 자바스크립트로 코딩테스트에서 출제될 수 있는 수들을 묶어서 최댓값 만들기 문제에 대해 다뤄보겠습니다. 이 문제는 다양한 알고리즘적 사고를 요구하며, 최적화 문제에 대한 이해를 깊이 있게 할 수 있는 기회를 제공합니다. 목표는 주어진 숫자들을 조합하여 가능한 최대 수를 만들어내는 것입니다.
문제 정의
주어진 수를 두 개 묶어서 곱하는 작업을 반복해 최댓값을 만들어내야 합니다. 자세한 문제 정의는 다음과 같습니다.
문제: N개의 자연수로 이루어진 배열이 주어질 때, 이 배열의 모든 수를 두 개씩 묶어서 곱하고 그 결과의 합을 최대화하는 프로그램을 작성하시오. 입력: - 첫 줄에 자연수 N (1 ≤ N ≤ 1000). - 둘째 줄에 N개의 자연수 a1, a2, ..., aN (1 ≤ ai ≤ 1000)가 주어짐. 출력: - 최댓값을 출력하시오.
문제 예시
입력: 5 1 2 3 4 5 출력: 43
문제 접근법
이 문제를 해결하기 위해서는 몇 가지 주요 단계가 필요합니다.
- 정렬: 주어진 수를 내림차순으로 정렬합니다. 가장 큰 수를 남겨두어 최대한 큰 곱 결과를 생성하기 위한 준비 단계입니다.
- 짝짓기: 배열에서 수를 두 개씩 묶어 곱하고, 그 결과를 모두 누적합니다. 짝짓기를 할 때는 가장 큰 두 수를 묶고, 그 다음 두 큰 수를 묶는 방식으로 진행합니다.
- 예외 처리: 홀수개의 수가 입력된 경우, 마지막 남은 수는 따로 처리하여 결과에 포함시켜야 합니다.
구현
자바스크립트로 이 문제를 해결하기 위한 코드를 작성해보겠습니다. 아래는 구현된 코드입니다.
function maxSumFromPairs(numbers) {
// 배열을 내림차순으로 정렬
numbers.sort((a, b) => b - a);
let maxSum = 0;
// 두 개씩 묶어서 곱하고 합산하기
for (let i = 0; i < numbers.length; i += 2) {
// 마지막 요소가 홀수일 경우, 남은 요소는 혼자 더함
if (i === numbers.length - 1) {
maxSum += numbers[i];
} else {
maxSum += numbers[i] * numbers[i + 1];
}
}
return maxSum;
}
// 예제 사용
const numbers = [1, 2, 3, 4, 5];
console.log(maxSumFromPairs(numbers)); // 43
코드 분석
코드의 각 부분을 분석해보겠습니다.
1. 정렬
먼저, 배열을 내림차순으로 정렬합니다. 이를 통해 더 큰 수가 먼저 오게 되고, 이를 기반으로 곱을 계산하게 됩니다. 자바스크립트에서 배열의 정렬은 sort 메소드를 사용하여 간단하게 수행할 수 있습니다.
2. 짝짓기 및 합산
반복문을 통해 배열의 요소를 두 개씩 읽어들이고, 그 곱을 maxSum에 누적합니다. 만약 배열의 길이가 홀수라면, 마지막 남은 요소는 보름의 수로 그냥 더해집니다.
3. 결과 반환
최종적으로 maxSum을 반환합니다. 코드는 간단하지만, 이로 인해 효율적으로 최댓값을 구할 수 있게 됩니다.
복잡도 분석
이 알고리즘의 시간 복잡도는 O(N log N)입니다. 이는 배열을 정렬하는 데 들어가는 시간 때문입니다. 이후의 반복문은 O(N)으로, 전체적으로 정렬을 제외한 연산은 선형입니다. 공간 복잡도는 O(1)로, 추가적인 공간을 사용하지 않으므로 메모리 효율도 좋습니다.
테스트 케이스
테스트 케이스를 몇 가지 추가하여 코드의 정확성을 검증해보겠습니다.
console.log(maxSumFromPairs([3, 5, 1, 2, 4])); // 47
console.log(maxSumFromPairs([1])); // 1
console.log(maxSumFromPairs([9, 7, 5, 3])); // 64
console.log(maxSumFromPairs([1, 1, 1, 1, 1])); // 5
결론
이번 글에서는 수를 묶어서 최댓값 만들기에 대한 문제를 다뤄보았습니다. 배열을 정렬하고, 최댓값을 구하는 방식으로 알고리즘을 구현했습니다. 이를 통해 배열의 즉각적인 처리를 어떻게 효율적으로 할 수 있는지에 대해 고민하게 되는 좋은 경험이 되셨기를 바랍니다.
자바스크립트를 사용한 코딩테스트에서는 이와 같은 최적화 문제들이 많이 출제되니, 꾸준한 연습이 필요합니다. 추가적으로 다양한 문제에 도전해보면서 알고리즘적 사고를 발전시켜 나가길 바랍니다!