leetcode 773(bfs), 23(merge k lists), 204(소수 구하기), 279(dp)

773 https://leetcode.com/problems/sliding-puzzle/

bfs로 모델링해서 푼다. 어려운 버전.

from collections import deque
class Solution(object):
    def slidingPuzzle(self, board):
        def bfs(x, y, board):
            queue = deque([[x, y, board[:], 0]])
            visited = set([''.join(map(str, board))])
            while queue:
                _x, _y, board, count = queue.popleft()
                _str = ''.join(map(str, board))
                if _str == '123450':
                    return count
                for __x, __y in [[-1, 0], [1, 0], [0, -1], [0, 1]]:  # 4방향
                    idx, idy = _x + __x, _y + __y
                    if not(0 <= idx <= 1) or not (0 <= idy <= 2):
                        continue

                    board[3*_x + _y], board[3*idx + idy] = board[3*idx + idy], board[3*_x + _y]
                    _str = ''.join(map(str, board))
                    if _str in visited:
                        board[3 * _x + _y], board[3 * idx + idy] = board[3 * idx + idy], board[3 * _x + _y]
                        continue
                    visited.add(_str)
                    queue.append([idx, idy, board[:], count + 1])
                    board[3*_x + _y], board[3*idx + idy] = board[3*idx + idy], board[3*_x + _y]
            # print 222
            return -1

        for i in xrange(2):
            for j in xrange(3):
                if board[i][j] == 0:
                    return bfs(i, j, [val for sublist in board for val in sublist])  # flatten해서 품. 이게 더 편해서.

23 https://leetcode.com/problems/merge-k-sorted-lists/

전부 가져온 뒤에 순회하면서 다시 만들어준다. https://qkqhxla1.tistory.com/1045에서 21번으로 풀었었는데, 저기 있는 방법론 중에 dummy를 처음에 놓고 cur은 현재 k개의 노드중에서 매번 가장 작은 값으로 sort해서 가져오도록 코드를 짰었는데, 테스트 케이스 중에 [[7],[49],[73],[58],[30],[72],[44],[78],[23],~~이런 케이스가 있어서 시간 초과로 성공을 못했다. discussion을 보니 heap에 넣고 힙소트로 푸는 경우도 있는데 heap도 매번 내부적으로 정렬을 하긴 하는데 전반적으로 비교를 하지 않는지 시간초과가 안뜨고 된다.

class Solution(object):
    def mergeKLists(self, lists):
        dummy = cur = ListNode(0)
        node_list = []
        for l in lists:
            while l:
                node_list.append([l, l.val])
                l = l.next

        node_list = sorted(node_list, key=lambda x: x[1])
        for i in xrange(len(node_list)-1):
            cur.next = node_list[i][0]
            cur = cur.next
        if node_list:
            cur.next = node_list[len(node_list)-1][0]
        return dummy.next

204 https://leetcode.com/problems/count-primes/

소수를 구한다.

class Solution(object):
    def countPrimes(self, n):
        if n < 3:
            return 0
        primes = [True] * n
        primes[0] = primes[1] = False
        for i in xrange(2, n):
            if primes[i]:
                for j in xrange(i * i, n, i):
                    primes[j] = False
        return sum(primes)

279 https://leetcode.com/problems/perfect-squares/submissions/

음 이거 좀 이상하다. 일단 문제는 아래처럼 풀었다. 근데 시간이 엄청 오래걸린다.

class Solution(object):
    def numSquares(self, n):
        dp = [0]
        for i in xrange(1, n+1):
            j = 1
            v = 9999999999
            while j*j < i+1:
                v = min(v, dp[i-j*j] + 1)
                j += 1
            dp.append(v)
        #print dp
        return dp[n]

그래서 효율적인 기법이 뭐가있나 살펴보고 있었는데..

https://leetcode.com/problems/perfect-squares/discuss/71512/Static-DP-C%2B%2B-12-ms-Python-172-ms-Ruby-384-ms

여기의 파이썬 코드를 보자. 

class Solution(object):
    _dp = [0]
    def numSquares(self, n):
        dp = self._dp
        while len(dp) <= n:
            dp += min(dp[-i*i] for i in range(1, int(len(dp)**0.5+1))) + 1,
        return dp[n]

이 코드는 속도가 엄청 빠른데, 희안하게 _dp = [0]을 바깥에 static으로 선언하고 dp = self._dp로 다시 갖고온다. 내부에서 그냥 dp = [0]처럼 선언해버리면 속도가 엄청나게 느리다. 사람들이 말하는걸 보면 static dp라고 하는데.... 왜 도대체 static으로 선언한 것 만으로 속도가 10배 이상 빨라지는지 이유를 모르겠다. 그냥 이런게 있다고 알아두자....