leetcode 1114(구현, 쓰레드), 417(dfs parcific atlantic water flow), 179(구현), 19(linked list)

1114 https://leetcode.com/problems/print-in-order/

쓰레드 환경에서의 lock관련된 실행 순서를 구현하는 문제이다.

반드시 first, second, third순으로 실행되게 하려면 lock으로 잠궜다 풀었다를 잘 해야 한다. lock.acquire()을 했을 경우 lock.release()를 호출해서 그 락을 풀어주기 전까지는 재차 lock.acquire()을 호출할수 없는점을 이용한다.

first에는 아무런 제한 없이 출력하고 풀어준다. second에는 first에서의 락을 acquire()함으로써 first에서 release()가 호출될때까지 기다려야함으로써 first -> second호출순서가 유지된다. third도 마찬가지이다.

from threading import Lock

class Foo:
    def __init__(self):
        self.locks = [Lock(), Lock()]
        self.locks[0].acquire()
        self.locks[1].acquire()
        
    def first(self, printFirst):
        printFirst()
        self.locks[0].release()
        
    def second(self, printSecond):
        self.locks[0].acquire()
        printSecond()
        self.locks[0].release()
        self.locks[1].release()
            
    def third(self, printThird):
        self.locks[1].acquire()
        printThird()
        self.locks[1].release()

https://leetcode.com/problems/print-in-order/discuss/335939/5-Python-threading-solutions-(Barrier-Lock-Event-Semaphore-Condition)-with-explanation 요 링크에 파이썬의 모든 동시성과 관련된 해답이 있다.

417 https://leetcode.com/problems/pacific-atlantic-water-flow/

분명 bfs dfs문제이고 bfs문제면 포맷이 다 비슷한데 오랫동안 제대로 풀지 못했다. 처음보는 포맷의 bfs dfs 문제였다.

물은 현재 좌표에서 높이가 같거나 낮은 쪽으로 흐른다고 했을때 parcific과 atlantic으로 둘다 흐르는 곳의 좌표들을 모아서 리턴하는 문제이다. 처음에는 모든 점을 다 돌아가면서 dfs로 pa나 at둘다 도달 가능한지를 판별해서 풀었는데 5000ms가 나왔다. 5000ms는 통과는 다 하는데 타임아웃이라는 뜻이어서 최적화를 해보려고 하다가 실패하고 discussion을 봤다.

그리고 나온 방법론.

왼쪽, 위쪽 벽이 parcific이므로 왼쪽 위쪽 edge부터 시작해서 물이 도달할수 있는곳들을 저장해놓는다.

오른쪽, 아래 벽이 atlantic이므로 오른쪽, 아래 edge부터 시작해서 물이 도달할수 있는곳들을 저장해놓는다.

그다음 이 두개의 교집합을 찾으면 그게 바로 그 점에서 pa, at둘다 갈수있는 좌표가 된다.

이 방법론으로 푸니 10배는 빨라졌다...

from collections import deque

class Solution(object):
    def pacificAtlantic(self, matrix):
        if not matrix:
            return []
        
        m, n = len(matrix), len(matrix[0])
        def dfs(stack, visited):
            while stack:
                x, y = stack.pop()
                cur_height = matrix[x][y]
                for _x, _y in [[-1, 0], [0, 1], [0, -1], [1, 0]]:
                    next_x, next_y = x + _x, y + _y
                    if (next_x, next_y) in visited or not 0 <= next_x < m or not 0 <= next_y < n or cur_height > matrix[next_x][next_y]:
                        continue
                    visited.add((next_x, next_y))
                    stack.append([next_x, next_y])
        
        pa = set()
        at = set()
        pas = deque()
        ats = deque()
        for i in xrange(m):
            pas.append([i, 0])
            pa.add((i, 0))
            ats.append([i, n-1])
            at.add((i, n-1))
        for i in xrange(n):
            pas.append([0, i])
            pa.add((0, i))
            ats.append([m-1, i])
            at.add((m-1, i))
            
        dfs(pas, pa)
        dfs(ats, at)
        return list(pa & at)

179 https://leetcode.com/problems/largest-number/

수를 조합해서 가장 큰 수를 구현하는 문제이다. 정렬을 하는데 파이썬으로 '123' > '12'이런식으로 비교가 가능하므로 

문자열로 비교했을때 큰 수를 앞으로 오게 하면 된다. 이걸 이용해서 조합했을때 숫자가 큰 순서대로 정렬한다.(cmp=lambda x,y: 1 if x+y < y+x부분.)

class Solution(object):
    def largestNumber(self, nums):
        nums = map(str, nums)
        nums = sorted(nums, cmp=lambda x,y: 1 if x+y < y+x else -1)
        return '0' if nums[0] == '0' else ''.join(nums)

19 https://leetcode.com/problems/remove-nth-node-from-end-of-list/

class Solution(object):
    def removeNthFromEnd(self, head, n):
        node_list = []
        while head:
            node_list.append(head)
            head = head.next
        
        node_list.pop(-n)
        for i in xrange(len(node_list)-1):
            node_list[i].next = node_list[i+1]
        if node_list:
            node_list[-1].next = None
        return node_list[0] if node_list else None