정수로 이루어진 두 배열 A와 B가 주어졌다고 가정해 봅시다. 이제 i번째 원소가 d * A[i] + B[i]로 정의되는 배열 C를 생각해 보겠습니다. 여기서 d는 임의의 실수입니다. 우리의 목표는 배열 C에 포함된 0의 개수가 최대가 되도록 하는 d 값을 찾고, 그때의 0의 개수까지 구하는 것입니다.
예를 들어 입력이 A = [15, 40, 45], B = [4, 5, 6]라면, 출력은 d = -0.266666...이 되고, 이때 0의 개수는 1개입니다.
문제 해결 접근 방식
핵심 아이디어는 간단합니다. C[i] = d * A[i] + B[i]가 0이 되려면 다음 조건을 만족해야 합니다.
d = -B[i] / A[i] (단, A[i] ≠ 0)
즉, 각 인덱스 i에 대해 해당 위치를 0으로 만들 수 있는 d 값을 계산한 뒤, 동일한 d 값이 몇 번 등장하는지 세면 됩니다. 가장 많이 등장하는 d 값이 곧 최대 개수의 0을 만들어 내는 답입니다.
특별한 경우로, A[i] == 0이면서 B[i] == 0인 원소는 어떤 d 값을 선택하더라도 항상 0이 되므로 별도로 카운트하여 마지막에 더해 줍니다.
알고리즘 단계
- n := 배열 A의 크기
- my_map := 새로운 딕셔너리(맵)
- count := 0
- i를 0부터 n-1까지 반복:
- B[i] ≠ 0이고 A[i] ≠ 0이면:
- val := (-1.0 * B[i]) / A[i]
- val이 my_map에 없으면 my_map[val] := 0으로 초기화
- my_map[val]을 1 증가
- B[i] == 0이고 A[i] == 0이면:
- count := count + 1 (모든 d에 대해 항상 0)
- B[i] ≠ 0이고 A[i] ≠ 0이면:
- maximum := 0
- my_map의 모든 항목을 순회하며 maximum을 최대 빈도 값으로 갱신
- my_map을 다시 순회하며 값이 maximum과 같은 첫 번째 키(d)를 출력하고 반복 종료
- 최종적으로 maximum + count를 출력
Python 구현 예제
다음 구현을 통해 더 잘 이해할 수 있습니다.
def find_d_zero(A, B):
n = len(A)
my_map = {}
count = 0
for i in range(n):
if (B[i] != 0 and A[i] != 0):
val = (-1.0 * B[i]) / A[i]
if val not in my_map:
my_map[val] = 0
my_map[val] += 1
elif (B[i] == 0 and A[i] == 0):
count += 1
maximum = 0
for item in my_map:
maximum = max(my_map[item], maximum)
for keys, values in my_map.items():
if (values == maximum):
print("d = ", keys)
break
print("Number of 0s: ", maximum + count)
a = [15, 40, 45]
b = [4, 5, 6]
find_d_zero(a, b)입력
[15, 40, 45], [4, 5, 6]
출력
d = -0.26666666666666666 Number of 0s: 1
복잡도 분석
시간 복잡도: O(n) — 배열을 한 번 순회하며 각 위치의 d 후보를 딕셔너리에 기록하고, 마지막에 딕셔너리를 한 번 더 순회하기 때문입니다.
공간 복잡도: O(n) — 최악의 경우 서로 다른 d 후보 값이 n개까지 저장될 수 있습니다.