DATA_STURCTURE1 DAY3

1.INTERSECTION OF TWO ARRAYS

class Solution(object):
    def intersect(self, nums1, nums2):
        answer=[]
        for i in range (len(nums1)):
            for j in range (len(nums2)):
                if nums1[i]==nums2[j]:
                    answer.append(nums1[i])
                    del nums2[j]
                    break
        return answer

처음엔 시간복잡도 생각안하고 좀 쉽게 풀려고 했으나 너무 속도가 느렸다
이중 반복문에서 같은 요소를 찾으면 정답에 추가하고 그 요소는 두번째 배열에서 빼는 형식으로 풀었다

두번쨰 답

class Solution(object):
    def intersect(self, nums1, nums2):
        obj={}
        arr= []
        def count (obj,n,nums):
            for i in range(n):
                try:
                    obj[nums[i]]+=1
                except :
                    obj[nums[i]]=1
        count(obj,len(nums1),nums1)
        for num in nums2:
            if num in obj and obj[num]>0:
                arr.append(num)
                obj[num]-=1
        return arr
        

딕셔너리 즉 객체를 활용해서 하니깐 훨씬 빨라졌다
시간복잡도는 배제고릴라하지 말자~

2.Best time to buy and sell stock

이 문제는 첫날에 푼 maximum-subarray랑 개념이 비슷했다
앞의 배열보다 지금 배열이 작으면 지금 배열을 기준으로 뒷 배열까지 연산
앞의 배열이 지금배열보다 크면 그 차이값이 전에 있던 제일 큰 차이값과 비교연산

class Solution(object):
    def intersect(self, nums1, nums2):
        obj={}
        arr= []
        def count (obj,n,nums):
            for i in range(n):
                try:
                    obj[nums[i]]+=1
                except :
                    obj[nums[i]]=1
        count(obj,len(nums1),nums1)
        for num in nums2:
            if num in obj and obj[num]>0:
                arr.append(num)
                obj[num]-=1
        return arr