leetcode 1769(prefix sum같은거), 1614, 1290(구현), 1315(트리)

1769 leetcode.com/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/
boxes배열이 있고, 1이면 공이 있고 0이면 공이 없다. i번째 배열에 모든 공을 모으려면 몇번 움직여야 하는지 합을 리턴하면 된다. 근데 당연히 무식하게 O(n^2)으로 하는게 의도가 아니라 O(n)으로 가능하다.
좋은 해설 : leetcode.com/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/discuss/1075895/Easy-Python-beats-100-time-and-space

class Solution(object):
    def minOperations(self, boxes):
        all_box_count,all_move = 0,0
        ret = [0] * len(boxes)
        for i in range(len(boxes)):
            all_move += all_box_count
            if boxes[i] == '1':
                all_box_count += 1
            ret[i] += all_move
            
        all_box_count,all_move = 0,0
        for i in range(len(boxes)-1, -1, -1):
            all_move += all_box_count
            if boxes[i] == '1':
                all_box_count += 1
            ret[i] += all_move
        return ret

왼쪽에서 오른쪽으로 가면서 합을 구해주고, 오른쪽에서 왼쪽으로 오면서 합을 구해준다음 전부 더해준다.

1614 leetcode.com/problems/maximum-nesting-depth-of-the-parentheses/
뭔가 스택을 사용하는 문제처럼 보이는 어디서 많이 본 문제이지만 가장 깊은 depth를 구하는 문제이다. 다른걸 구할필요도 없이 ()만 보고 depth를 구하면 되므로, (가 나올때는 +1을, )가 나오면 -1을 해주면서 가장 깊었을때의 값을 저장하면 된다.

class Solution(object):
    def maxDepth(self, s):
        ret = 0
        max_ret = 0
        for ss in s:
            if ss == '(':
                ret += 1
                max_ret = max(max_ret, ret)
            elif ss == ')':
                ret -= 1
        return max_ret

1290 leetcode.com/problems/convert-binary-number-in-a-linked-list-to-integer/
왼쪽 자리일수록 2의 제곱배므로 매번 2씩 곱해주고 이후 자릿수를 더해준다.

class Solution(object):
    def getDecimalValue(self, head):
        cur = head
        ret = 0
        while cur:
            ret = ret * 2 + cur.val
            cur = cur.next
        return ret

1315 leetcode.com/problems/sum-of-nodes-with-even-valued-grandparent/
조부모 노드가 짝수이면 손자 노드들의 합을 더해주면 된다. 큐에 현 노드, 부모 노드, 조부모 노드들을 유지해가며 계산한다.

class Solution(object):
    def sumEvenGrandparent(self, root):
        ret = 0
        queue = [[root, None, None]]
        while queue:
            node, parent, grand_parent = queue.pop(0)
            if grand_parent and grand_parent % 2 == 0:
                ret += node.val
            for child in [node.left, node.right]:
                if child:
                    queue.append([child, node.val, parent])
        return ret