Input Array Is Sorted

문제

오름차 순으로 이미 정렬된 정수 배열인 1-인덱스 배열 numbers가 주어집니다. 특정 타겟 숫자와 합산되는 두 숫자를 찾으세요. 이 두 숫자를 numbers[index1]과 numbers[index2]라 하겠습니다. 여기서 1 <= index1 < index2 < numbers.length입니다.

길이가 2인 정수 배열 [index1, index2] 형태로 두 숫자의 인덱스, index1과 index2를 반환하세요. 테스트는 정확히 하나의 해결책이 있는 방식으로 생성하되 같은 요소를 두 번 사용하면 안되고 상수의 추가 공간만을 사용해야 합니다.

---

접근 방향

numbers 배열 안에 있는 요소들 중 두 요소를 덧셈한 값이 target의 숫자와 동일한 경우를 찾고 두 요소의 인덱스가 담긴 배열을 반환하는 문제로 가장 먼저 들었던 생각은 배열의 요소들 중 두 요소를 덧셈하여 타겟의 수를 도출해야 하므로 타겟보다 큰 요소를 배제한 범위만큼만 값을 더해 타겟과 동일한 경우를 확인해야겠다고 생각이 먼저 들었습니다. 하지만 이 경우 타겟이 음수일 경우를 생각하여 음수일 때는 타겟보다 작을 경우 작은 요소를 탐색 범위에서 제외해야 합니다. 이렇게 필터링 작업을 거쳤다면 이후 앞에서 뒤로 진행하는 포인터와 뒤에서 앞으로 진행하는 포인터를 두고 덧셈을 한 값이 타겟과 동일할 때 해당 인덱스를 배열에 넣어 반환하도록 합니다.

나의 풀이

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """

        # 타겟이 0보다 클 때, 0보다 작을 때, 0일 때로 나눕니다.
        if target > 0:
            cp_numbers = [x for x in numbers if x <= target]
        if target < 0:
            cp_numbers = [x for x in numbers if x >= target]
        if target == 0:
            cp_numbers = numbers

        # 만약 위에서 필터링하였을 때 길이가 2일 경우, 두 요소의 합이 타겟과 동일한 경우이므로 해당 요소의 인덱스를 배열에 넣어 반환합니다.
        if len(cp_numbers) == 2:
            return [numbers.index(cp_numbers[0]) + 1, numbers.index(cp_numbers[1]) + 1]
        else:
            # 그렇지 않을 경우, 두 포인터로 나누어 앞에서 뒤로, 뒤에서 앞으로 각각 순회합니다.
            start = 0
            end = -1
            while start < len(cp_numbers) // 2:
                # 앞에서 순회
                for num in cp_numbers[start+1:]:
                    # 만약 두 값이 같을 경우 중복이므로, 마지막 인덱스에 2를 덧셈
                    # 오름차순 정렬이 전제되어 있으므로 [start+1, start+2]로 반환할 수도 있음
                    if cp_numbers[start] + num == target:
                        if cp_numbers[start] == num:
                            return [start+1, numbers.index(num)+2]
                        return [start+1, numbers.index(num)+1]
                # 뒤에서 순회
                for num in cp_numbers[:end]:
                    if cp_numbers[end] + num == target:
                        return [numbers.index(num)+1, len(cp_numbers)+end+1]

                start += 1
                end -= 1

두번째 풀이

class Solution(object):
  def twoSum(self, numbers, target):
    """
    :type numbers: List[int]
    :type target: int
    :rtype: List[int]
    """
    if target > 0:
      cp_numbers = [x for x in numbers if x <= target]
    if target < 0:
      cp_numbers = [x for x in numbers if x >= target]
    if target == 0:
      cp_numbers = numbers

    if len(cp_numbers) == 2:
      return [numbers.index(cp_numbers[0]) + 1, numbers.index(cp_numbers[1]) + 1]
    else:
      # 첫 번째 인덱스
      start = 0
      # 마지막 인덱스
      end = len(numbers) - 1

      while start < end:
        # 두 인덱스 요소의 총합
        cur_sum = numbers[start] + numbers[end]
        # 두 인덱스 요소의 총합이 target과 동일할 경우 두 인덱스를 배열로 반환
        if cur_sum == target:
          return [start + 1, end + 1]
        # 현재 총합이 타겟보다 작을 경우 오름차순이므로 start를 증가
        elif cur_sum < target:
          start += 1
        # 현재 총합이 타겟보다 클 경우 두 요소의 덧셈값을 낮춰야하므로 end를 감소
        else:
          end -= 1