7 분 소요

Two Pointers

문제

문제 링크

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 < numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6 Output: [1,3] Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1 Output: [1,2] Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Constraints:

  • 2 <= numbers.length <= 3 * 104
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in non-decreasing order.
  • -1000 <= target <= 1000
  • The tests are generated such that there is exactly one solution.

스스로 고민

접근법

  • 배열에서 타겟 넘버를 만들 수 있는 요소 두 개의 합을 찾는다.
  • 두 개의 합을 만들 수 있는 요소의 인덱스를 리턴한다.
  • 제한 사항은 똑같은 원소 두번 사용금지
  • 추가적인 공간은 사용가능하다.

    아는 패턴

  • 처음에 이걸 투 포인터로 어떻게 찾지? 라고 생각을 했다.

  • 근데 투 포인터면 분명히 이게 효율적인 방식이기 때문에 무조건 답이 있을거라고 생각을 곰곰히 해봤다.

  • 처음에는 타겟 넘버보다 낮은 값들 뽑아서 거기서 비교하면 될거라 생각했는데 음수를 생각 못 했다.
    • 어쩐지 너무 쉽다고 생각했다.
    • 근데 또 바꿔서 생각해보면 타겟넘버를 기준점으로 오른쪽과 왼쪽으로 나누면 될거 같았다. 왜냐하면 타겟이 0이라면 어차피 음수 값과 양수 값을 더 하면 된다.
    • 근데 또 조건을 다시 보니 -1000 <= target <= 1000 이였다.
    • 그럼 0을 기준으로 나누면 해결 될거 같았다. 왜냐면 타겟값이 -100 이라고 가정한다면 0을 기준으로 양수와 음수를 더한 값을 찾고 답이 없다면 음수끼리 더하는 식으로 하면 될거 같았다.
    • 일단 무지성으로 코드를 작성하고 혹시나 마이너스 값 끼리 더하거나 플러스 끼리 더해서 타겟 넘버가 나오는 경우가 오류로 나올 경우….음.. 나중에 다시 생각해보기로 했다.

의사코드

  • 0을 기준으로 front와 back 을 나눈다.
  • 오름차순으로 정렬 되어 있으니 가장 낮은 값과 큰 값을 더해서 값을 찾으면 된다.
  • 타겟 값이 + 와 - 를 더 해서 나올 경우
  • +, + , - , - 이렇게 3가지 경우를 나눠서 해봤다.

구현 코드

class Solution:

    def twoSum(self, numbers, target):

  

        plus = [x for x in numbers if x >= 0]

        minus = [x for x in numbers if x < 0]

        for i in range(len(plus)):

            for r in range(len(minus)):

                if plus[i] + minus[r] == target:

                    return numbers.index(minus[r])+1, numbers.index(plus[i])+1

        for i in range(len(plus)):

            for r in range(len(plus)):        

                if plus[i] + plus[r] == target:

                    return numbers.index(plus[i])+1, numbers.index(plus[r])+1

  

        for i in range(len(minus)):

            for r in range(len(minus)):  

                if minus[i] + minus[r] == target:

                    return numbers.index(minus[i])+1, numbers.index(minus[r])+1
  • 같은 엘리먼트 두 번 안된다고 해서 중복이 없는줄 알았는데
  • [0,0,3,4] 이렇게도 나온다.
class Solution:
    def twoSum(self, numbers, target):
        plus = [x for x in numbers if x >= 0]
        minus = [x for x in numbers if x < 0]
        answer = []

        if len(plus) != 0 and len(minus) != 0:
            for i in range(len(plus)):
                for r in range(len(minus)):
                    if plus[i] + minus[r] == target:
                        answer = [numbers.index(minus[i]) + 1, numbers.index(plus[r]) + 1]
                        return answer
        elif len(minus) == 0:
            for i in range(len(plus)):
                for r in range(len(plus)):
                    if plus[i] + plus[r] == target:
                        answer = [numbers.index(plus[r]) + 1, numbers.index(plus[i]) + 1]
                        if answer[0] == answer[1]:
                            num_indices = {}  
                            for i, num in enumerate(numbers, start=1):
                                complement = target - num
                                if complement in num_indices:
                                    return [num_indices[complement], i]
                                num_indices[num] = i
                            
                        else:
                            return answer
        else:
            for i in range(len(minus)):
                for r in range(len(minus)):
                    if minus[i] + minus[r] == target:
                        answer = [numbers.index(minus[i]) + 1, numbers.index(minus[r]) + 1]
                        return answer
  • 0 을 기준으로 나눴을 경우 [-1000,-1,0,1] , 타겟 값이 1인 경우 이런 조건에서는 답을 찾지 못한다
    • 왜냐하면 양수 음수로 나눴는데 답은 양수 안에서만 찾아야 되기 때문이다.
    • 어떻게 하면 2개 포인트로 나눠서 값을 잘 찾을 수 있을까
    • 사실 그냥 무지성으로 반복문 두 개 쓰면 해결되긴 하는데 더 좋은 방법이 있을거라고 생각했다.
  • 우선 조건을 다시 설정해봤다
    • [0,0,1,2] , 타겟 = 0 처럼 0이 두 번 나오는 경우
    • [-10,-1,1,2,3,10] 타겟= 2 -> 음수랑 양수랑 더해야 되는 경우
    • [1,2,3,4,5] 타겟 7 -> 양수에서만 나오는 경우
    • [-111,-19,-9,-5] 타겟 -24 -> 음수에서만 값이 나오는 경우
  • 새로운 조건 의사코드
    • 왼쪽과 오른쪽을 이동 시킬 변수 a,b 선언
    • while 문에 사용할 변수 x 선언 -> 답이 나오면 멈추고 답이 안나오면 계속 반복
    • 0,0 이 나오거나 8,8 처럼 같은 수가 나오는 경우는 인덱스 값을 똑바로 못 찾는다 그러나 내림차순으로 정렬 되어 있고 인덱스를 찾을 때 가장 빠른걸 찾으니 처음 찾은 인덱스 번호는 a, 거기에 1을 더해 b 값을 만들어서 위와 같은 경우를 해결한다.
    • 만약 현재 왼쪽과 오른쪽을 더했을 때 값이 타겟 값보다 작다면 왼쪽이 작은 수 혹은 음수 이므로 왼쪽을 오른쪽으로 한칸 이동시키고 그 반대의 경우에는 오른쪽을 한칸 왼쪽 쪽으로 이동시킨다.
class Solution:

    def twoSum(self, numbers, target):
        a = 0
        b = -1
        x = None
        
        while x != target:
            x = numbers[a] + numbers[b]
            if numbers[a] == numbers[b]:

                a = numbers.index(numbers[a])+1
                b = a+1

                return a, b

            elif x < target:
                a +=1

            else:
                b -=1

        return a+1, numbers.index(numbers[b+1])+1

시간 복잡도와 공간 복잡도

  • 시간 복잡도는 while 문 한 개를 사용해서 O(n), numbers.index() 도 배열을 추가적으로 한 번 순회해서 시간복잡도는 O(n)
    • O(n) + O(n) = O(n)
  • 공간 복잡도는 a,b,x 등의 변수는 고정된 공간을 차지하므로 공간 복잡도는 O(1)

회고 과정

지금 코드에서 뭘 개선할 수 있지?

  • 반복문과, 상수 지정을 안하고 더 개선을 할 수 있는 방법이 딱히 떠오르지 않았다.
  • 사실 처음에 무지성으로 삽질하는 상태에서 계속 생각하면서 다시 코드를 작성한거라 여기서 더 좋은 생각이 떠오르지가 않아서 다른 사람이 만든 코드를 보면서 깨닫는 게 더 좋다고 생각했다.

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        num_dict = {}
        for i, num in enumerate(numbers):
            complement = target - num
            if complement in num_dict:
                return [num_dict[complement] + 1, i + 1]
            num_dict[num] = i

        # The function will only reach this point if no such pair is found
        return []
  • 해시맵 (딕셔너리) 를 사용해서 해결한 방법이다.
  • 시간 복잡도와 공간 복잡도는 다르지 않지만 첫 번째 방법은 점진적으로 합을 구하고 비교하지만 이 방법은 딕셔너리로 한 번의 반복으로 문제를 해결할 수 있다.
  • 타겟 값에서 현재 값을 뺀후 딕셔너리에 저장한다. 현재 돌아가는 반복문에서 나오는 값이 저장된 딕셔너리 안에 값이 존재한다면 답이 있다는 뜻이다.
  • 답이 나오게 된다면 현재 값은 인덱스이므로 인덱스 +1 을 해줘서 리턴하고 딕셔너리에 있는 벨류 값으로 인덱스를 추출해서 +1 을 해준 후 리턴해주면 된다.

그럼 언제 해시맵을 사용하면 좋을까?

해시맵의 개념:

  • 해시맵은 특정한 키(key)에 대한 값을 빠르게 검색하고 저장하기 위한 자료구조다.
  • 내부적으로 해시 함수를 사용하여 키를 해시(해싱)하여 값의 인덱스를 계산하므로 매우 빠른 검색이 가능하다.

해시맵을 사용하는 이유:

  1. 빠른 검색: 해시맵은 평균적으로 O(1) 시간에 검색이 가능하다. 이는 매우 큰 데이터 집합에서도 빠른 검색을 가능하게 하다.
  2. 고유한 키: 해시맵은 각 키를 고유하게 처리한다. 이는 중복을 허용하지 않는 경우에 유용하다.
  3. 유연한 데이터 관리: 데이터의 추가, 삭제, 수정이 빠르게 가능하며, 데이터를 관리하고 조작하기에 용이하다.
  4. 문제 해결에 활용 가능: 많은 문제가 특정 값에 대한 키를 찾거나, 두 값 간의 관계를 빠르게 파악해야 하는 상황에서 해시맵은 유용하게 사용된다.

해시맵의 사용 예:

  1. 데이터 저장: 데이터베이스에서 데이터를 검색하거나 메모리 내에서 데이터를 관리할 때 사용된다.
  2. 중복 제거: 중복된 값을 필터링하거나 중복 체크에 사용될 수 있다.
  3. 빠른 검색: 특정 값을 검색하거나 관련된 정보를 빠르게 찾아야 할 때 사용된다.
  4. 문제 해결: 알고리즘 문제에서 빠른 값을 찾거나 조작해야 하는 상황에서 유용하게 활용된다.

해시맵을 사용하면 데이터를 효율적으로 관리하고 검색하는 것이 가능해진다. 따라서 두 번째 코드에서 사용한 방식처럼 해시맵을 활용하는 것이 데이터 검색과 관리 측면에서 더 효율적이며 권장되는 방법으로 생각해 볼 수 있다.

댓글남기기

참고