leetcode 416(backtracking), 658(이분 탐색), 205(구현), 290(구현)

https://leetcode.com/problems/partition-equal-subset-sum/

문제를 못풀었다. discussion에서 답들을 읽어보다 이 백트래킹 답이 가장 이해하기 쉬워서 이걸 공유한다.

https://leetcode.com/problems/partition-equal-subset-sum/discuss/90610/Python-Backtracking-with-Memoization-Solution

답을 봐도 좀 빡세서 이해하는데 한참걸렸다.

class Solution(object):
    def canFindSum(self, nums, target, ind, n, d):  # 남은 nums배열, target, index, 끝길이, d=캐시
        if target in d: return d[target]  # 이미 target을 탐색한적이 있으면 리턴함.
        if target == 0: d[target] = True  # target이 0으로 되면 현재 target는 만들수 있으므로 True로 set함.
        else:
            d[target] = False  # 기본적으로 False로 만들어놓고,
            if target > 0:  # target이 0보다 작은 경우에는 이미 만들기 불가능하므로 0보다 큰 경우만 탐색함.
                for i in xrange(ind, n):  # 똑같은 index탐색을 막기 위해 인덱스값을 넘겨서 재귀함.
                    if self.canFindSum(nums, target - nums[i], i+1, n, d):  # 다음에 탐색할 target은 target - nums[i]임. 이 값이 탐색가능하면 현재 target도 탐색가능함. 
                        d[target] = True
                        break
        return d[target]
    
    def canPartition(self, nums):
        s = sum(nums)
        if s % 2 != 0: return False  # subset이 반씩 쪼개져야 하므로 2로 나눠지지 않으면 False임.
        return self.canFindSum(nums, s/2, 0, len(nums), {})

658 https://leetcode.com/problems/find-k-closest-elements/

아이디어를 생각하다가 discussion을 보고 이분 탐색으로 풀었다.

1. x와 가장 가까운 k개의 수를 arr에서 가져와야한다. 단순히 x와 가장 가까운 수를 정렬된 리스트 arr에서 가져오려면 이분 탐색을 하면 된다. 근데 k개를 가져오려면 조금 더 생각해야 한다. 

2. k개를 가져와야 하므로 left = 0, right = len(arr)-k에서 이분탐색을 시작한다.

x의 위치가 x-arr[mid]-arr[mid+k]처럼 arr[mid], arr[mid+k]의 사이에 있지 않고 벗어나서 왼쪽에 있거나,

x의 위치가 arr[mid]-x-arr[mid+k]처럼 중간에 껴 있는 경우에는 x가 arr[mid+k]보다 arr[mid]와 가까운 경우에는 right의 범위를 중앙으로 좁혀준다. 

3. 2번의 경우가 아니면 다 left를 mid로 옮긴

class Solution(object):
    def findClosestElements(self, arr, k, x):
        l, r = 0, len(arr)-k
        while l < r:
            mid = (l + r) // 2
            if x <= arr[mid] < arr[mid + k] or \
                x - arr[mid] <= arr[mid + k] - x:
                r = mid
            else:
                l = mid + 1
        return arr[l:l+k]

근데 https://leetcode.com/problems/find-k-closest-elements/discuss/106426/JavaC%2B%2BPython-Binary-Search-O(log(N-K)-%2B-K) 그냥 중간 판별부분을 

if x - A[mid] > A[mid + k] - x:
                left = mid + 1
            else:
                right = mid

처럼만 처리해도 된다.

205 https://leetcode.com/problems/isomorphic-strings/

면접 손코딩에서 나올만한 가벼운 문제이다.

class Solution(object):
    def isIsomorphic(self, s1, s2):
        def encode(string):
            d = {}
            ret_str = ''
            counter = 0
            for s in string:
                if s not in d:
                    d[s] = counter
                    counter += 1
                ret_str += str(d[s])
            return ret_str
        return encode(s1) == encode(s2)

와 근데 discussion에 대단한 답이 있음 ㅡㅡ;

https://leetcode.com/problems/isomorphic-strings/discuss/57838/1-line-in-Python

def isIsomorphic(self, s, t):
    return len(set(zip(s, t))) == len(set(s)) == len(set(t))

290 https://leetcode.com/problems/word-pattern/

290번은 바로 위의 205번의 코드들을 조합하면 된다..

class Solution(object):
    def wordPattern(self, pattern, ss):
        def encode(string):
            d = {}
            ret_str = ''
            counter = 0
            for s in string:
                if s not in d:
                    d[s] = chr(97 + counter)
                    counter += 1
                ret_str += str(d[s])
            return ret_str
        s,t = encode(ss.split()), pattern
        return len(set(zip(s, t))) == len(set(s)) == len(set(t)) and len(s) == len(t)