UNIST, CSE 3th

2 minute read

55. Jump Game (Medium)

재귀함수와 DP를 이용하여 풀었으나, Time Exceeded가 떠버려서, 다른 방식으로 풀었다. 간단하게 마지막 인덱스에 도달 할 수 있는지만 확인하면 되는것이기에 뒤쪽 인덱스부터 for문을 사용하여 마지막 인덱스에 도달 할 수 있는지 체크하였다.

# DP를 이용한 풀이
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        dp = [False] * len(nums)
        return self.help(dp, 0, nums)

    def help(self, dp, index, nums: List[int]) -> bool:
        if index >= len(nums) - 1:
            return True
        if dp[index]:
            return True

        res = False        
        for i in range(1, nums[index] + 1):
            res |= self.help(dp, index + i, nums)

        dp[index] = res
        return dp[index]

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        last_index = len(nums) - 1
        for i in range(last_index, -1, -1):
            if i + nums[i] >= last_index:
                last_index = i
        return last_index <= 0

1382. Balance a Binary Search Tree (Medium)

우리가 수업에서 배웠던 AVL Tree와는 다른 balancing 방식이어서 생소했다. 원래는 right, left rotating 을 이용하거나 2-3 Tree에서 사용하는 방식을 이용했는데 이 문제의 핵심은 그냥 ‘모든 elements’ 들이 Tree에만 들어가면 되기 때문에 간단하게 DFS를 이용해서 모든 원소를 배열에 담고, 그 배열을 Binary Search 하듯이 Tree를 다시 만들어서 반환하였다.

class Solution:
	def balanceBST(self, root: TreeNode) -> TreeNode:
		v = []
		def dfs(node):
			if node:
				dfs(node.left)
				v.append(node.val)
				dfs(node.right)
		dfs(root)

		def bst(v):
			if not v:
				return None
			mid = len(v) // 2
			root = TreeNode(v[mid])
			root.left = bst(v[:mid])
			root.right = bst(v[mid + 1:])
			return root

		return bst(v)

1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits (Hard)

어려운 문제이다. 간단한 DFS로도 풀리지 않고 DP를 써도, Greedy를 써도 잘 안풀린다. 아마 조금의 꼼수가 필요한듯 한데. 일단 문제를 다 풀지는 않았지만 조금이라도 생각의 여지를 남겨야 다음에 풀 수 있을 것 같아서 남긴다. 처음 접근한 방식은 당연하게도 swap 했을때 숫자가 작아진다면 DFS를 이용하여 recursive하게 적용하여 최소값을 찾는것이다.

class Solution:
    def minInteger(self, num: str, k: int) -> str:
        n = len(num)
        res = int(num)
        res_str = num
        if k == 0:
            return num

        # 4321 - 3421 - 3241 - 2341 - 2314
        # 4321 - 4312 - 4132 - 1432 - 1342

        # print(num)
        for i in range(n - 1):
            a, b = ord(num[i]), ord(num[i + 1])
            if a > b:
                # swap
                a, b = num[i], num[i + 1]
                temp = self.minInteger(num[:i] + b + a + num[i + 2:], k - 1)
                if int(temp) < res:
                    res_str = temp
                    res = int(temp)
        return res_str

내가 생각한 가장 단순하고 쉬운 방법이었으나, k가 20을 넘어가면 터져버리게된다. 그래서 다른 방법을 고안한게 가장 작은 digit을 가장 앞쪽으로 당겨와서 그만큼의 k를 소모시킨다음 위와 같은 방식으로 문제를 해결하는 것이다. ‘0’ 과 같은 문자는 가장 앞쪽에 있는게 맞기 때문에, 이걸 우선적으로 처리하면 알고리즘이 조금이나마 빨라지지 않을까 싶다. 이런 추잡한(?) 방식외에 한번에 깔끔하게 해결할 수 있는 방법은 떠오르질 않는다. 아쉽게도, 내일 문제를 본다면 풀 수 있기를 바랄뿐이다.

You may also enjoy