[Leetcode] 1769. Minimum Number of Operations to Move All Balls to Each Box
21-12-06
solved
Problem
You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the ith box is empty, and '1' if it contains one ball.
In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1. Note that after doing so, there may be more than one ball in some boxes.
Return an array answer of size n, where answer[i] is the minimum number of operations needed to move all the balls to the ith box.
Each answer[i] is calculated considering the initial state of the boxes.
문제 유형은 잘 모르겠다. 그냥 array인가보다. 오늘 daily challenge 문제, Q.1271가 easy 이길래, medium 하나 더 풀려고 challenge 문제와 연관된 문제를 풀었다. 사실 이 1769번도 acceptance가 되게 높은 축에 속한다.
이 문제를 brute force로 풀면 time complexity O(n^2)이 나오는데 O(n)이 나오는 것을 목표로 풀어보려고 했다.
Solution
class Solution:
def minOperations(self, boxes: str) -> List[int]:
ans=[0]
leftZero=0
rightZero=0
for i,v in enumerate(boxes):
if v=="1":
ans[0]+=i
rightZero+=1
if boxes[0]=="1":
leftZero=1
rightZero-=1
#print(ans)
for i,v in enumerate(boxes[1:],start=1):
#print(i,v)
val=ans[-1]-rightZero+leftZero
ans.append(val)
if v=="1":
leftZero+=1
rightZero-=1
return ans
스트링을 처음부터 끝까지 한 번 읽어서 ans[0]을 우선 먼저 계산한다. 그 다음 중요한 것은 iteration 과정에서 왼쪽에 있는 0의 개수(leftZero)와 오른쪽에 있는 0의 개수(rightZero)이다.
val=ans[-1]-rightZero+leftZero
이 부분이 가장 중요하다. iteration하는 문자 기준으로 오른쪽에 있는 0 개수만큼은 전체 거리가 가까워 지고, 왼쪽에 있는 0 개수만큼 전체 거리가 멀어지기 때문에 위와 같은 val이 결정된다.
for i,v in enumerate(boxes[1:],start=1):
개인적으로 기억하고 싶은 코드는 위 코드이다. enumerate할 때, index 1부터 읽고 싶을 때, 위와 같이 하면 된다.
Another Solution
class Solution:
def minOperations(self, boxes: str) -> List[int]:
n = len(boxes)
answer = [0] * n
curr, steps = 0, 0
for i in range(n):
answer[i] += steps
curr += int(boxes[i])
steps += curr
curr, steps = 0, 0
for i in reversed(range(n)):
answer[i] += steps
curr += int(boxes[i])
steps += curr
return answer
자기보다 왼쪽에 있는 1 개수를 answer[i]에 담는다. 이 때, 1 개수는 누적되기 때문에, steps에 저장할 수 있다.(일종의 dp로 볼 수 있다.) O(N)이 소모된다.
이제 반대로 자기보다 오른쪽에 있는 1 개수를 answer에 저장한다. 이 과정도 O(N)이 소모된다.
한 번 정방향으로 읽었다가, 반대 방향으로 읽는 풀이가 종종 보인다. 기억해뒀다가, 나도 다음에 써먹어야겠다.
서버 만드는 과제하러 가야하는데, 많이 어렵다. 조금 막막하다. 차근차근 해내야겠다.
Author And Source
이 문제에 관하여([Leetcode] 1769. Minimum Number of Operations to Move All Balls to Each Box), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jong_p/Leetcode-1769.-Minimum-Number-of-Operations-to-Move-All-Balls-to-Each-Box저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)