leetcode 227(basic calculator), 1197(bfs, dp등), 1010(2sum 다른버전), 526(dp)

227 https://leetcode.com/problems/basic-calculator-ii/
이전 부호의 상태값을 저장해놨다가 그걸 기반으로 푼다. 이런 계산기반의 문제는 보통 부호를 한번 저장해놓고 다음단계에 가져와서 쓰는식으로 하는것 같다. 하드문제인 https://leetcode.com/problems/basic-calculator/ 와 비교해보면서 익히자.

class Solution:
    def calculate(self, s: str) -> int:
        num = 0
        stack = []
        sign = '+'
        i = 0
        while i < len(s):
            #print(s[i],stack)
            if s[i].isdigit():
                num = num * 10 + int(s[i])
            if s[i] in '+-*/' or i == len(s) - 1:
                if sign == '+':
                    stack.append(num)
                elif sign == '-':
                    stack.append(-num)
                elif sign == '*':
                    stack.append(stack.pop()*num)
                else:
                    tmp = stack.pop()
                    if tmp//num < 0 and tmp%num != 0:
                        stack.append(tmp//num+1)
                    else:
                        stack.append(tmp//num)
                sign = s[i]
                num = 0
            i += 1
        return sum(stack)

1197 https://leetcode.com/problems/minimum-knight-moves/
처음 풀었을때 bfs로 코드는 짰지만 거의 타임아웃수준의 시간이 나왔다. 최적화와, 여러가지의 정답이 있었다.

1. bfs.
bfs로 풀때 단순하게 x,y로 갈수 있는 모든 방향으로 가게 해놓고, 간곳은 visited로 처리하면 너무너무 오래걸린다. 그래서 최적화를 해야하는데 x,y를 전부 양수로 만든다음에 음수로 가는 길은 안가도록 하게해도 된다.
이유 : x,y좌표가 예시로 2,1이 주어져있다. 그러면 1번에 갈수 있다. 하지만 x,y좌표가 -2,-1이면? 그래도 1번에 갈수 있다. 숫자만 음수일뿐 방향은 동일하기 때문이다. x,y 둘중하나 가 음수값이라 해도 둘다 양수인 좌표로 가는것과 카운트는 동일하므로 무조건 양수로 만들수있다. -2, 1로 간다해도 2,1가는것과 동일하게 1번이다.
그러니까 목적지인 x,y를 양수로 만든 후에, 다음 갈수있는 방향중에 (-2, -1), (-1, -2)케이스는 뺄수있다.(정 반대로 가는 케이스이므로) 그리고 이동해야할 위치와 목적지간의 거리가 일정 이상으로 벌어져도 쓸모없는 케이스가 되버리므로 그냥 가지 않도록 처리하면 속도가 압도적으로 빨라진다.

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        x,y = abs(x), abs(y)  # 목적지를 양수로 만들어줌. 양수나 음수나 상관없으므로 계산하기 쉽게 양수로 만들어준다.
        queue = [[0, 0, 0]]
        visited = {(0, 0)}
        while queue:
            temp_x, temp_y, move = queue.pop(0)
            if temp_x == x and temp_y == y:
                return move
            for _x, _y in [[1, -2], [2, -1], [2, 1], [1, 2], [-1, 2],
                                 [-2, 1]]:  # (-2, -1), (-1, -2)는 목적지와 아예 반대방향이므로 안 가도 됨.
                next_x, next_y = temp_x + _x, temp_y + _y
                if (next_x, next_y) not in visited and \
                    (-1 <= next_x <= x+2 and -1 <= next_y <= y+2):  # 일정이상 벗어나면 방문할 필요가 없음.
                    visited.add((next_x, next_y))
                    queue.append([next_x, next_y, move + 1])

2. dp. https://leetcode.com/problems/minimum-knight-moves/discuss/387120/Python3-Clear-short-and-easy-DP-solution-No-Need-for-BFS-or-math
이것도 똑똑하다. 1번과 비슷하게 둘다 양수로 만들어버린후, 어차피 이동은 1,2 또는 2,1로만 하므로 목적지 x,y에서 -1,-2나 -2,-1 후의 결과값중 작은 것만 리턴한다. x,y를 빼다가 둘다 0이 되버리면 그게 끝부분이 되버리니 0을 리턴했고, x,y의 합이 2인 경우만 2번 스텝을 더 가야하는 경우로 신경써주면 된다.
x+y의 합이 2인 경우는 목적지가 (1, 1), (-1, -1), (-1, 1), (1, -1) 인 경우 모두 양수로 만들어버리니 (1,1)인 경우인데 이 경우에는 0,0에서 2번 이동해야 도달 가능하다. 이걸 dp의 초기값으로 생각하면 된다. 합이 2가 아니라 1인 경우인(0,1),(1,0)같은 경우는 합이 2인 경우보다 나중에 나오는 케이스다. 이후로 dp리스트에 값을 저장하면서 푼다. 와 이걸생각못했네..

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        dp = [[0]*301 for i in range(301)]
        def DP(x,y):
            if x + y == 0:
                return 0
            elif x + y == 2:
                return 2
            elif dp[x][y] != 0:
                return dp[x][y]
            dp[x][y] = min(DP(abs(x-1),abs(y-2)),DP(abs(x-2),abs(y-1)))+1
            return dp[x][y]
        return DP(abs(x),abs(y))

3. 이건 그냥 미친듯 ㅋㅋㅋㅋㅋㅋ 실제 인터뷰에서는 쓰지 않을 방법인데 그냥 대단하다 : https://leetcode.com/problems/minimum-knight-moves/discuss/392053/Here-is-how-I-get-the-formula-(with-graphs) 

1010 https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/
2 sum문제처럼 푼다. 인덱스 0의 값이 20이라고 하면 20과 합친 수가 60으로 나눠질 pair는 (60-20)%60인 40이다.(마지막에 60으로 나눈 나머지를 붙이는 이유는 수의 범위가 1~500이기 때문.) 리스트를 초기화하고, pair가 이전에 존재한 값만큼 더한후 다음 시기에 검증할때 현재 인덱스의 값을 사용해야 하므로 현재 값(t%60)을 1 올려준다. t%60인 이유는 위와 마찬가지로 수의 범위가 1~500이기 때문이다.

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        c = [0]*60
        res = 0
        for t in time:
            pair = (60-t)%60
            res += c[pair]
            c[t%60] += 1
        #print(c)
        return res

526 https://leetcode.com/problems/beautiful-arrangement/
딱 봐도 dp문제인데, 처음에 n이 n-1의 영향을 받을거라 생각해서 삽질을 좀 했다. 굳이 n이 n-1의 영향을 받을거라 생각하지 말고 n이 최대 15이므로 재귀로 모든 케이스를 구하되, 한번 구했었던 값은 또 계산하지 말고 가져오는 방식으로 짜면 된다.
1. 리스트 n을 하나씩 줄여나가는 방법론은 문제에서처럼 특정 인덱스 i번째가 아름다운 정렬 조건을 만족할 시에 그 i번째 인덱스의 값만 제외하고 나머지로 새 리스트를 만들어서 돌려준다.
2. 끝조건은 n == 1인경우 무조건 1이므로 1을 리턴해준다.

class Solution:
    dp = {}
    def countArrangement(self, n: int) -> int:
        def get_arr(n, t):
            if n == 1:
                return 1
            key = '{}_{}'.format(n, tuple(t))
            if key in self.dp:
                return self.dp[key]
            
            _sum = 0
            for i in range(len(t)):
                if n % t[i] == 0 or t[i] % n == 0:
                    #print(t,t[:i])
                    _sum += get_arr(n-1, t[:i] + t[i+1:])
            self.dp[key] = _sum
            return self.dp[key]
        return get_arr(n, list(range(1, n+1)))