Algorithm
Problem
Two Sum

문제

Two Sum

정수 배열 nums와 정수 target이 주어졌을 때, 합이 target이 되는 두 수의 인덱스를 반환하세요.

각 입력에서 정확히 하나의 답이 있다고 가정할 수 있으며, 동일한 요소를 두 번 사용할 수 없습니다.

답을 임의의 순서로 반환할 수 있습니다.

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
 
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
 
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 10^4
-109 <= nums[i] <= 10^9
-109 <= target <= 10^9
Only one valid answer exists.

떠올릴 수 있는 접근 방법

  • 완전탐색(2중포문)
    • Big O (n^2)
def twoSum(nums,target):
  n = len(nums)
  for i in range(n-1):
    for j in range(i+1,n):
      if nums[i] + nums[j] == target:
        return True
  return False
 
print(twoSum(nums=[4,1,9,7,5,3,16],target=14))

완전탐색 접근방법은 주어진 제약조건을 생각했을 때 시간초과가 날 수 있다.(10^8), 다른 접근 방법을 떠올려야함.

정렬 적용하기

  1. 오름차순으로 정렬한다.
  2. 배열의 양쪽 끝을 포인터로 잡고 더해서 타겟넘버를 구한다.
  3. 더한 값이 타겟넘버보다 크다면 오른쪽 값을 한칸 옮긴다.
  4. 더한 값이 타겟넘버보다 작다면 왼쪽 값을 한칸 옮긴다.
  5. 포인터의 인덱스가 같아진다면 반복문을 종료한다.

코드로 구현하기

def solution(nums,target):
  nums.sort()
  l,r = 0, len(nums)-1
  while l<r:
    if nums[l] + nums[r] > target:
      r -=1
    elif nums[l] + nums[r] < target:
      l +=1
    elif nums[l] + nums[r] == target:
      return True
 
  return False
 
print(solution(nums=[4,1,9,7,5,3,16],target=14))

문제에 적용하는 경우

  1. 선형 자료구조 + 중간에 데이터 추가 / 삭제 용이
  2. Tree or Graph에 활용

딕셔너리로 풀어보기

메모리를 사용해서 시간복잡도를 줄여보자 똑똑한 뇌 접근 방법, 만약 자료구조 상 모든 값을 기억할 수 있다면 좋지 않을까? Big O(1)으로 접근 가능하기 때문에

nums = {4,1,9,7,5,3,16}
def solution()
Longest Consecutive SequenceValid Parentheses