leetcode 953(구현), 1249(스택), 295(find median value)

953 https://leetcode.com/problems/verifying-an-alien-dictionary/

 

시키는대로 구현한다.

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        d = {o: i for i, o in enumerate(order)}
        words = [[d[w] for w in word] for word in words]
        for i in range(max(len(w) for w in words)):
            check = [word[i] if len(word) > i else -1 for word in words]
            check = list(zip(check, check[1:]))
            if all(a < b for a,b in check):
                return True
            elif any(a > b for a,b in check):
                return False
        return True

1249 https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/

 

적절하지 않은 괄호를 삭제한다. 괄호 삭제부터 이전 스택문제와 비슷해서 스택으로 풀었다.

class Solution(object):
    def minRemoveToMakeValid(self, s):
        """
        :type s: str
        :rtype: str
        """
        stack = set()
        ret = []
        for i, ss in enumerate(s):
            if ss == '(':
                stack.add(i)
            elif ss == ')':
                if not stack:
                    continue
                stack.pop()
            ret.append([i, ss])
            
        ret = [r[1] for r in ret if r[0] not in stack]
        return ''.join(ret)

답들을 살펴보다가 창의적인 답 발견.. 없애야 하는 문자들을 *로 만든뒤에 재조합하고 replace로 *를 지워버린다. 속도가 내 코드보다 3배는 빠르다.

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        s = list(s)         
        stack = []         
        for i, c in enumerate(s):         
            if c == '(':                 
                stack.append(i) 
            elif c == ')':                 
                if stack:                     
                    stack.pop()                 
                else:                     
                    s[i] = '*'         
        for i in stack:             
            s[i] = '*'
        return ''.join(s).replace('*', '') 

295 https://leetcode.com/problems/find-median-from-data-stream/

 

답을 보고 이해했다. 최소힙, 최대 힙을 사용해서 중간값을 유지해준다.

https://leetcode.com/problems/find-median-from-data-stream/discuss/74047/JavaPython-two-heap-solution-O(log-n)-add-O(1)-find

 

동작 방식. 

최소 힙의 루트에는 항상 최소 값만 유지되고, 최대 힙의 루트에는 항상 최대 값만 유지된다. 이를 이용한다.

1. 최소 힙과 최대 힙의 길이가 같으면 먼저 최소 힙에 데이터를 음수로 바꿔서 넣은 후 최소 힙에서 가장 작은 값을 빼서 다시 최대 힙에 넣는다.

최소 힙에 값을 넣을때 음수로 바꿔서 넣는 이유는 최소 힙의 root가 가장 작은 값이므로, 음수로 바꿔 넣음으로서 root를 최대값으로 유지하기 위해서이다.(빼낼때는 다시 -를 붙여서 빼내면 되고, 음수로 넣음으로써 최대 힙처럼 동작하게 된다.)

 

2. 최소 힙과 최대 힙의 길이가 다르면 최대 힙에 데이터를 넣어준다. 최대 힙은 가장 큰 값이 루트에 유지되기 때문에 이렇게 넣어주고, 데이터를 넣음과 동시에 최대 힙에서의 가장 큰 데이터를 pop해서 최소 힙에 다시 넣어준다.

 

이걸 반복하면 6, 10, 2, 6, 5, 0, 6, 3, 1, 0, 0 를 넣었을 경우 

최대힙 = self.small = [-2, -1, 0, 0, 0] -> 루트에 -2가 있는 이유는 우리가 값을 -로 변환해서 넣음으로서 최소힙을 최대힙처럼 사용했기 때문.

최소힙 = self.large = [3, 6, 5, 10, 6, 6]

이렇게 데이터가 유지된다. 힙의 0번째 인덱스가 루트이므로 최대힙의 루트와 최소힙의 루트가 자연스럽게 median값을 유지하게 된다. (최대힙은 0~중간까지의 값을 유지하고, 최소힙은 중간~최댓값까지를 유지하므로.)

 

코드 저장해둠.

from heapq import *

class MedianFinder:
    def __init__(self):
        self.small = []  # the smaller half of the list, max heap (invert min-heap)
        self.large = []  # the larger half of the list, min heap

    def addNum(self, num):
        if len(self.small) == len(self.large):
            heappush(self.large, -heappushpop(self.small, -num))
        else:
            heappush(self.small, -heappushpop(self.large, num))

    def findMedian(self):
        if len(self.small) == len(self.large):
            return float(self.large[0] - self.small[0]) / 2.0
        return float(self.large[0])