DATA STRUCTURE1 DAY2

1. Two Sum

이 문제는 이중 반복문에서 target과 같을 때 찾으면 되는 문제였다

 class Solution(object):
     def twoSum(self, nums, target):
         for i in range (len(nums)):
            for j in range (i+1,len(nums)):
               if nums[i]+nums[j]==target:
                    return [i,j]

실행 속도가 그렇게 빠르지 않았고 다른 답들을 찾아보니

enumurate를 사용해서 index를 넣는 풀이가 좋았다

class Solution(object):
       def twoSum(self, nums, target):
        d = {}
        for i, n in enumerate(nums):
            m = target - n
            print(i,n)
            if m in d:
                return [d[m], i]
            else:
                d[n] = i

속도도 내가 한 것보다 15프로 더 높았던 것 같았다

2.Merge Sort Array

문제 제약조건이 num1을 변형해서 리턴하라는 문제여서
나는 queue형식을 차용해 풀었다

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        for i in range (len(nums1)-m):
            nums1.pop()
        for i in range (n) :
            nums1.append(nums2.pop(0))
        return nums1.sort()

그냥 문제 형식대로 구현을 해서 풀었다
일단 nums1을 m개만 있게 추출한 다음
나머지 n개이 nums2를 넣고 sort 돌려서 마무리를 지었다.
!!하지만 이 문제 출제의도는 두 배열의 상관관계를 생각해서 푸는 것이었다
즉 pointer를 생각했었어야 한다

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        while m > 0 and n > 0:
            if nums1[m - 1] > nums2[n - 1]:
                nums1[m + n - 1] = nums1[m - 1]
                m -= 1
            else:
                nums1[m + n - 1] = nums2[n - 1]
                n -= 1
        nums1[:n] = nums2[:n]

두 배열의 제일 끝 요소를 비교해서 만들어야하는 배열의 최상단부터 넣어준다 그리고 while문을 나가고 n의 개수가 남아있으면 nums2에서 가져오는 방식이다