leetcode 39(backtracking), 1353(그리디), 128(two pointer), 368(lis)

39 https://leetcode.com/problems/combination-sum/
별다른 설명이 필요 없다. 백트래킹 연습용으로 좋은 문제다.

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        #candidates = [1,2]
        #target = 4
        
        ret = []
        def get_comb(candidates, cand, target):
            if target == 0:
                ret.append(cand)
                return
            for i in range(len(candidates)):
                if target-candidates[i] >=0:
                    get_comb(candidates[i:], cand + [candidates[i]], target-candidates[i])
        get_comb(candidates, [], target)
        return ret

1353 https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/
모든 이벤트들을 시작일 기준으로, 그다음엔 끝나는 날 기준으로 정렬한 후에 시작일을 하나하나 돌아가면서 같은 시작일일 경우 그 이벤트들의 끝나는 날짜를 최소 힙에 저장해둔다. 그다음 최소 힙에서 pop하면 '같은 시작일이면서 빨리 끝나는 이벤트' 순으로 pop이 될것이므로 이것을 이용해서 최대한 많은 이벤트를 참석할수 있도록 조율한다.

from heapq import *

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        #events= [[1,2],[1,2],[1,6],[1,2],[1,2]]
        
        events.sort(key=lambda x:(x[0], x[1]))  # 이벤트들을 시작일 기준으로, 그다음엔 끝나는 일 기준으로 정렬한다.
        end_day = max([e[1] for e in events])  # 모든게 끝나는 날짜
        heap = []
        ret = 0
        cur_day = -1
        i = 0
        while cur_day <= end_day:
            if cur_day == -1:  # cur_day를 초기화해준다.
                cur_day = events[i][0]  # cur_day는 현재 존재하는 가장 빨리 시작하는 이벤트의 시작일.
            while i < len(events) and events[i][0] == cur_day:  # 시작일이 같은 이벤트들을 먼저 처리하기 위해 힙에 저장해둔다.
                heappush(heap, events[i][1])  # 시작일이 같은 이벤트들의 끝나는 날짜만 힙에 저장해둔다. 빨리 끝나는거부터 처리하기 위함
                i += 1
            # [[1,2],[1,2],[1,6],[1,2],[1,2]] 같은 예외케이스를 처리하기 위함.
            # 이벤트의 끝나는 날이 이미 지나갔으면(cur_day보다 작으면) 참석 못하는거니 그냥 버린다.
            while heap and heap[0] < cur_day:
                heappop(heap)
            if heap:  # 참석할 이벤트가 있으면 참석한다.
                ret += 1
                heappop(heap)
            cur_day += 1
        return ret

 
128 https://leetcode.com/problems/longest-consecutive-sequence/
[-1, -1, 0, 1, 3, 4, 5, 6, 7, 8, 9] 와 같은 리스트가 있다고 할 경우 증가하는 부분집합들은 (-1, 0, 1), (3,4,5,6,7,8,9) 가 있다. 이것들을 찾으려면 two pointer로 앞점과 뒷점을 만든 후, 앞점 + 1 == 뒷점인 경우 한칸씩 뒤로 증가시켜주면서 길이를 늘려주되, 앞점 + 1 != 뒷점이면 길이를 다시 1로 초기화해주면 된다.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        #nums = [9,1,4,7,3,-1,0,5,8,-1,6]
        if not nums:
            return 0
        nums.sort()  # 오름차순 정렬
        
        ret = -1
        i = 0
        while i < len(nums):  # 모든 경우에 대해서 계산
            _len = 1
            _prev, _next = i, i+1  # _prev는 two pointer의 앞점, _next는 뒷점이 될 예정
            while _next < len(nums):
                while _next < len(nums)-1 and nums[_prev] == nums[_next]:  # lcs의 뒷점이 앞점과 같으면 다른곳까지 가라고 늘려준다.
                    _next += 1
                if nums[_prev] + 1 == nums[_next]:  # 앞점과 뒷점이 1 차이이면 길이를 1 늘려준다.
                    _len += 1
                else:  # 앞점과 뒷점의 차이가 1 초과면 길이를 초기화해준다.
                    _len = 1
                ret = max(ret, _len)
                _prev = _next  # 앞점을 이전 뒷점으로,
                _next += 1  # 뒷점을 1 증가신후 다시 판별
            i = _prev + 1
        return ret

368 https://leetcode.com/problems/largest-divisible-subset/
O(n^2) lis와 같은 방법론으로 풀수 있다. 

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        #nums = [5,9,18,54,108,540,90,180,360,720]
        nums.sort()
        ret = [[n] for n in nums]
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] % nums[j] == 0 and len(ret[i]) < len(ret[j])+1:
                    ret[i] = ret[j] + [nums[i]]
        return sorted(ret, key=lambda x: -len(x))[0]

300번이 lis문제인데 https://leetcode.com/problems/longest-increasing-subsequence/ 이것을 O(n^2)으로 풀면 아래와 같다.

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        #nums = [10,9,2,5,3,7,101,18]
        ret = [1]*len(nums)
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] > nums[j] and ret[i] < ret[j] + 1:
                    ret[i] = ret[j] + 1
        return max(ret)