[2024] day 173. Leetcode 1552. Magnetic Force Between Two Balls
2024년부터 새롭게 다시 시작하는 코딩테스트
2024년 6월 20일 (목)
Leetcode daily problem
1552. Magnetic Force Between Two Balls
Problem
우주 지구 C-137에서 Rick은 두 개의 공을 자신이 새로 발명한 바구니에 넣으면 사이에 특별한 형태의 자기력이 있음을 발견했다. Rick은 n개의 빈 바구니를 가지고 있고, i번째 바구니는 위치[i]에 있고, Morty는 m개의 공을 갖고 있으며 두 공 사이의 최소 자기력이 최대가 되도록 공을 바구니에 분배해야 한다.
x와 y 위치에 있는 서로 다른 두 공 사이의 자기력은 |x - y|이다.
정수 배열 positions과 정수 m이 주어질 때, 필요로 하는 힘을 반환한다.
Solution
greedy, binary search
자석으로 인해 볼 사이에 발생하는 힘을 최대화 하는 문제인데,
특정 위치에 있는 자석들 사이에 최대한 균등하게 힘을 배치하는 것으로 즉, 볼이 주어진 수 만큼 선택해서 두 볼 사이의 최소 거리를 최대화 한다.
두 볼 사이의 최소 거리를 최대화하기 위해 가능한 거리의 값을 이진 탐색으로 찾아내고 이를 그리디 알고리즘과 결합하여 해결한다.
주어진 볼들의 위치의 배열 position을 오름차순으로 정렬하고,
최소길이 1, 최대 길이를 (최대 위치-최소 위치)로 설정한다.
중간 값을 설정하고 이 거리가 유효한지를 판단하여, 유효하면 최소 거리를 중간값+1로 해 더 큰 최소 거리를 탐색하고 유효하지 않은 경우 최대 길이를 중간값-1로 해서 더 작은 최소 길이를 탐색한다.
여기서 유효한 거리 인지 아닌 지를 그리디로 탐색하는데,
현재 최소 거리인 중간값이 유효한지 확인하기 위해서 그리디 방식으로 볼을 배치한다.
첫 번째 볼을 배치해서 다음 볼을 중간값 이상의 거리로 배치해서 확인한다.
Code
class Solution:
def maxDistance(self, position: List[int], m: int) -> int:
def IsPlacedBall(dist):
cnt = 1
prev_pos = position[0]
for i in range(1, len(position)):
if position[i] - prev_pos >= dist:
cnt +=1
prev_pos = position[i]
if cnt == m:
return True
return False
position.sort()
l,r = 1, position[-1] - position[0]
while l<=r:
mid = (l+r)//2
if IsPlacedBall(mid):
l = mid+1
else:
r = mid-1
return rComplexicity
시간 복잡도
주어진 position 배열을 정렬하는 과정에서 O(nlogn) 이 소요되고,
이진 탐색을 하면서 log(max_dist) 가 소요된다. max_dist는 position배열의 -1, 0 번째 인덱스의 합이다.
각 이진 탐색시 마다 볼을 확인하는 함수를 호출하는데 position 배열의 한번 순홰해서 m 개의 공을 배치할 수 있는 지 확인하므로 O(n)이 소요된다.
즉, 전체 시간 복잡도는 이진 탐색을 주축으로 해서 O(n log(max_dist)) 이다.
공간 복잡도
position 배열을 정렬하면서 O(n)의 공간이 필요하고 나머지는 상수 변수를 사용한다.
전체 공간 복잡도는 O(n)이다.
