문제 개요
n개의 요소로 이루어진 배열 A가 있다고 가정해 보겠습니다. 우리가 찾아야 할 것은 0이 아닌 정수 d로, 배열의 모든 숫자를 d로 나눈 뒤 결과 배열에 남아 있는 양수의 개수가 배열 전체 크기의 절반(올림 값) 이상이 되도록 하는 값입니다. 조건을 만족하는 d가 여러 개라면 그중 어떤 하나만 반환하면 됩니다.
예를 들어 입력이 A = [10, 0, -7, 2, 6]라고 해봅시다. n = 5이므로 나눗셈 이후 최소 ⌈5/2⌉ = 3개의 양수가 존재해야 합니다. 이 프로그램은 1을 반환합니다. 실제로 d = 1로 나누면 배열은 [10, 0, -7, 2, 6] 그대로 유지되고, 양수인 10, 2, 6 세 개의 요소가 남기 때문입니다. 참고로 d = 2나 d = 4 같은 값 역시 조건을 충족하지만, 문제의 요구사항상 가능한 답 중 하나만 반환하면 충분합니다.
풀이 접근 방법
핵심 관찰은 다음과 같습니다. 0이 아닌 정수 d로 나눈다고 해서 요소의 부호가 사라지지는 않습니다. 양수로 나누면 부호가 그대로 유지되고, 음수로 나누면 양수와 음수가 서로 뒤바뀔 뿐입니다. 또한 0은 어떤 수로 나눠도 여전히 0입니다. 따라서 나눗셈 후 만들 수 있는 최대 양수 개수는 '원래 양수 개수' 또는 '원래 음수 개수' 중 더 큰 값이며, 이 값조차 절반에 미치지 못한다면 조건을 만족하는 d는 존재하지 않습니다.
이 성질을 이용하면 다음 단계로 문제를 해결할 수 있습니다.
- 양수 개수를 저장할 z와 음수 개수를 저장할 f를 0으로 초기화합니다.
- 배열 A의 크기를 n에 저장한 뒤, 모든 요소를 한 번씩 순회하면서 요소가 양수이면 z를, 음수이면 f를 1씩 증가시킵니다.
- 순회가 끝난 후 2 * z >= n이면 1을 반환합니다. 양수가 이미 절반 이상이므로 d = 1이면 충분하기 때문입니다.
- 그렇지 않고 2 * f >= n이면 -1을 반환합니다. d = -1로 나누면 기존의 음수들이 모두 양수로 바뀌기 때문입니다.
- 두 조건을 모두 만족하지 않으면 0을 반환합니다. 이는 어떤 0이 아닌 정수로 나눠도 조건을 달성할 수 없다는 의미입니다.
C++ 구현 예시
아래 구현을 통해 더 자세히 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
int z = 0, f = 0;
int n = A.size();
for (int i = 0; i < n; i++){
int a = A[i];
if (a > 0)
z++;
if (a < 0)
f++;
}
if (2 * z >= n)
return 1;
else if (2 * f >= n)
return -1;
else
return 0;
}
int main(){
vector<int> A = { 10, 0, -7, 2, 6 };
cout << solve(A) << endl;
}입력
{ 10, 0, -7, 2, 6 }출력
1
복잡도 분석
배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 별도의 추가 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다. 단순한 카운팅과 비교만으로 답을 결정하기 때문에 매우 효율적인 풀이입니다.