leetcode 97(dfs), 767(구현, 힙), 991(구현), 650(dp)

97 https://leetcode.com/problems/interleaving-string/

 

dfs로 푼다. 

from collections import deque

class Solution(object):
    def isInterleave(self, s1, s2, s3):
        s1_len, s2_len, s3_len = len(s1), len(s2), len(s3)
        if s1_len + s2_len != s3_len:
            return False
        
        stack = deque([[0, 0]])
        visited = set()
        visited.add((0, 0))
        
        while stack:
            p = stack.pop()
            if p[0] + p[1] == s3_len:
                return True
            if p[0] < s1_len and s1[p[0]] == s3[p[0] + p[1]] and (p[0]+1, p[1]) not in visited:
                stack.append([p[0]+1, p[1]])
                visited.add((p[0]+1, p[1]))
            if p[1] < s2_len and s2[p[1]] == s3[p[0] + p[1]] and (p[0], p[1]+1) not in visited:
                stack.append([p[0], p[1]+1])
                visited.add((p[0], p[1]+1))
        return False

767 https://leetcode.com/problems/reorganize-string/submissions/

 

단어를 빈도순으로 힙에 넣은 후 가장 많은 빈도순으로 두개를 빼서 합쳐준다. 그리고 한개씩만 카운트를 낮춘 후 다시 힙에 넣어준다. 둘중 작은 카운트만큼 반복후 작은 카운트 단어를 없애버리는 방법론은 aabbcc같은걸 풀수가 없다.

from collections import Counter
from heapq import *

class Solution:
    def reorganizeString(self, s: str) -> str:
        ret = ''
        heap = []
        for k, v in Counter(s).items():
            heappush(heap, [-v, k])
        
        c1,n1,c2,n2 = '', 0, '', 0
        while len(heap) > 1:
            n1,c1 = heappop(heap)
            n2,c2 = heappop(heap)
            
            ret += c1 + c2
            
            if n1 < -1:
                heappush(heap, [n1+1, c1])
            if n2 < -1:
                heappush(heap, [n2+1, c2])
        if heap:
            if heap[0][0] < -1:
                return ''
            ret += heap[0][1]
        
        return ret

991 https://leetcode.com/problems/broken-calculator/

 

처음에는 startValue에서 시작해서 target에 도달하도록 dfs를 구현했는데 1 10000000같은 케이스는 경우의 수가 많아져서 타임아웃이 나버린다. 타임아웃이 나버리고 깨달은건 startValue에서 시작하는게 아니라 target을 줄여나가는 방법론으로 해야한다는거다.
2로 나누는 연산이 가장 빨리 줄일수 있는 방법이므로 2로 나눠지면 2로 나누고, 아니면 1을 더해준다. 2로 안나눠지면 1을 빼는게 아니라 더하는 이유는 첫번째 예시인 2 -> 4 -> 3으로 가는것처럼 구현하기 위해서이다.

class Solution:
    def brokenCalc(self, startValue: int, target: int) -> int:
        ret = 0
        while target > startValue:
            ret += 1
            if target % 2 == 0:
                target //= 2
            else:
                target += 1
        return ret + startValue - target

650 https://leetcode.com/problems/2-keys-keyboard/

 

위 문제와 비슷하다. dp로 푼다. 바로 위의 991과 다르게 이건 dp로 푸는데 n의 범위가 1000이하이다. 대부분 이런 경우 O(n^2)의 시간복잡도까지 허용한다고 본다.(O(n^2)이어봤자 100만이므로.) 그리고 991과는 다르게 이 문제는 이전 상태값이 필요하다.
6의 최소값은, min(이전 6일때의 값, 6으로 나눠지는수일때의 값 + 6/6으로 나눠지는 수 ) 이다. 아래 소스코드로 봤을때 i//j를 더해주는 이유는 복사하고 붙여넣는 카운트의 정도가 i//j이기 때문이다.

class Solution:
    def minSteps(self, n: int) -> int:
        if n == 1:
            return 0
        elif n == 2:
            return 2
        
        dp = [9999999]*(n+1)
        dp[1] = 0
        dp[2] = 2
        for i in range(3, n+1):
            for j in range(1, i):
                if i % j == 0:
                    dp[i] = min(dp[i], dp[j] + i//j)
        
        return dp[-1]