nums라는 이름의 배열이 있다고 가정해 보겠습니다. 이때 우리가 구해야 할 것은 배열에 포함된 모든 요소를 곱한 결과의 부호입니다.
예를 들어 입력이 nums = [-2, 3, 6, -9, 2, -4]라고 한다면, 전체 곱은 -2592가 되므로 출력 결과는 "Negative"(음수)가 됩니다.
문제 해결 접근 방법
흥미로운 점은 실제로 모든 숫자를 일일이 곱할 필요가 없다는 것입니다. 부호만 판별하면 되기 때문에, 배열을 한 번만 순회하면서 0의 개수와 음수의 개수만 세면 됩니다.
다음 단계에 따라 문제를 해결할 수 있습니다.
- zeroes(0의 개수)와 negatives(음수의 개수)를 각각 0으로 초기화합니다.
- 배열의 각 요소 i에 대해 다음을 수행합니다.
- i가 0이면 zeroes를 1 증가시킵니다.
- i가 0보다 작으면 negatives를 1 증가시킵니다.
- zeroes가 0보다 크면(즉, 0이 하나라도 존재하면) "Zero"를 반환합니다.
- 그렇지 않고 negatives를 2로 나눈 나머지가 0이라면, 즉 음수의 개수가 짝수라면 "Positive"를 반환합니다.
- 위 조건에 해당하지 않으면(음수의 개수가 홀수라면) "Negative"를 반환합니다.
동작 원리
이 방법이 성립하는 이유는 수학적 성질 때문입니다.
- 곱셈에서 피연산자 중 하나라도 0이면 결과는 반드시 0이 됩니다.
- 음수끼리 곱하면 양수가 되므로, 음수의 개수가 짝수이면 최종 곱은 양수입니다.
- 반대로 음수의 개수가 홀수이면 최종 곱은 음수입니다.
덕분에 오버플로우 걱정 없이 O(n) 시간 복잡도로 빠르게 답을 구할 수 있습니다.
구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
def solve(nums):
zeroes, negatives = 0, 0
for i in nums:
if i == 0:
zeroes += 1
if i < 0:
negatives += 1
if zeroes > 0:
return "Zero"
elif negatives % 2 == 0:
return "Positive"
else:
return "Negative"
nums = [-2, 3, 6, -9, 2, -4]
print(solve(nums))입력
[-2, 3, 6, -9, 2, -4]
출력
Negative
입력 배열에는 음수가 3개(-2, -9, -4) 있고 0은 없습니다. 음수의 개수가 홀수이므로 함수는 "Negative"를 반환하며, 이는 실제 곱인 -2592의 부호와 일치합니다.