문제 설명
주어진 정수 배열에서 두 개의 수를 선택하여 곱한 값을 구하고, 이와 같은 방식으로 가능한 모든 조합의 곱 중에서 최댓값을 찾아야 합니다. 단, 배열의 길이는 1 이상 105 이하이며, 각 원소의 값은 -109 이상 109 이하입니다.
입력 형식
첫 번째 줄: 정수 n (배열의 크기)
두 번째 줄: n 개의 정수 (배열의 원소)
출력 형식
최댓값을 출력한다.
문제 풀이 과정
본 문제는 두 수의 곱을 최대화하는 과정을 통해 수를 묶는 방법론을 적용하는 알고리즘 문제입니다. 이 문제를 해결하기 위해서는 다음과 같은 몇 가지 단계를 거쳐야 합니다.
1. 데이터 분석
우선 우리가 가진 수들의 성질을 살펴보겠습니다. 양수의 경우, 큰 두 수를 곱하는 것이 최댓값을 만드는데 유리합니다. 반면 음수의 경우, 두 개의 음수를 곱하면 양수가 되므로 두 개의 가장 작은 음수를 이용하는 것이 최댓값을 구하는 데 유리합니다. 이를 종합하면 다음과 같은 두 가지 경우를 고려해야 합니다:
- 가장 큰 두 양수의 곱
- 가장 작은 두 음수의 곱
2. 알고리즘 설계
위의 경우를 바탕으로 알고리즘을 설계할 수 있습니다. 우선 배열의 모든 원소를 탐색하여 양수와 음수를 분리한 후, 각각의 최대값과 최소값을 찾습니다.
- 양수들 중에서 가장 큰 두 수를 찾습니다.
- 음수들 중에서 가장 작은 두 수를 찾습니다.
- 각각의 곱을 비교하여 최댓값을 구합니다.
3. 코틀린 구현
이제 위 알고리즘을 코틀린으로 구현해 보겠습니다.
fun maxProduct(numbers: IntArray): Long {
val positives = mutableListOf()
val negatives = mutableListOf()
for (num in numbers) {
if (num > 0) {
positives.add(num)
} else if (num < 0) {
negatives.add(num)
}
}
positives.sortDescending()
negatives.sort()
var maxProduct = Long.MIN_VALUE
if (positives.size >= 2) {
maxProduct = maxOf(maxProduct, positives[0].toLong() * positives[1])
}
if (negatives.size >= 2) {
maxProduct = maxOf(maxProduct, negatives[0].toLong() * negatives[1])
}
return maxProduct
}
4. 테스트 케이스
이제 작성한 함수를 검증하기 위한 몇 가지 테스트 케이스를 작성해 보겠습니다.
fun main() {
// 테스트 케이스1: 모든 수가 양수
println(maxProduct(intArrayOf(1, 2, 3, 4))) // 출력: 12
// 테스트 케이스2: 모든 수가 음수
println(maxProduct(intArrayOf(-1, -2, -3, -4))) // 출력: 6
// 테스트 케이스3: 혼합된 수
println(maxProduct(intArrayOf(-1, 2, -3, 4))) // 출력: 6
// 테스트 케이스4: 결합된 수
println(maxProduct(intArrayOf(-10, -20, 5, 3, -2))) // 출력: 200
// 테스트 케이스5: 0 포함
println(maxProduct(intArrayOf(0, -5, -1, 2))) // 출력: 5
}
결론
이번 강좌에서는 ‘수를 묶어서 최댓값 만들기’ 문제를 통해 알고리즘 설계 과정과 코틀린 프로그래밍 기법을 배워 보았습니다. 이 문제는 배열 내 원소들을 분석하고 분리하는 기본적인 데이터 처리 방법을 연습하는 기회를 제공합니다. 이후 코틀린을 통해 실질적으로 구현함으로써 이론이 실제로 어떻게 적용되는지를 이해하는 데 큰 도움이 되었기를 바랍니다. 앞으로도 다양한 문제를 통해 알고리즘 실력을 키워 나가길 바랍니다.