#167 Two Sum II - Input Array Is Sorted

문제링크 - https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

문제 조건

• 2 <= numbers.length <= 3 * 10^4
• -1000 <= numbers[i] <= 1000
• numbers는 오름차순으로 정렬되어야 한다.
• -1000 <= target <= 1000
• 배열에 정담은 하나만 있다.
  int 배열과 int target을 입력 받아 해당 target을 만드는 배열의 index 두개를 배열로 출력해야한다.

문제 해결

문제 해결 로직

해당 문제는 정렬된 numbers 배열에서 두 Index를 가지고 조합을 찾을 수 있다.
앞과 뒤에서 현재 Index 위치의 값들의 합과 target의 값을 비교하여 Index 위치를 옮긴다.

데이터 입력

문제에서 입력이 들어오는 데이터는 String s 하나지만 위치 관리를 위해 필요한 변수를 미리 선언해야한다.

• startIndex
  앞에서 부터 세는 index
• endIndex
  뒤에서 부터 세는 index
• index
  결과 인덱스를 저장할 int 배열

인덱스 변경

현재 numbers의 배열이 오름차순으로 정렬되어 있기 때문에 다음과 같이 투 포인터를 사용할 수 있다.

• 합이 target보다 작은 경우
  • startIndex를 뒤로 이동한다.(합이 커지는 것을 기대)
• 합이 target보다 큰 경우
  • endIndex를 앞으로 이동한다.(합이 작아지는 것을 기대)
• 합이 target과 같은 경우
  • 해당 index를 결과 배열에 저장하고 반복문 종료

if(numbers[startIndex]+numbers[endIndex] < target){
	startIndex++;
}else if(numbers[startIndex]+numbers[endIndex] > target){
    endIndex--;
} else{
    result[0] = ++startIndex;
    result[1] = ++endIndex;
    break;
}

코드 작성

class Solution {
  public int[] twoSum(int[] numbers, int target) {
    int startIndex = 0;
    int endIndex = numbers.length - 1;
    int result[] = {0,0};

    while(startIndex < endIndex){
      if(numbers[startIndex]+numbers[endIndex] < target){
        startIndex++;
      }else if(numbers[startIndex]+numbers[endIndex] > target){
        endIndex--;
      } else{
        result[0] = ++startIndex;
        result[1] = ++endIndex;
        break;
      }
    }
    
    return result;
  }
}

복잡도 계산

• 시간 복잡도

  • 배열의 길이를 n이라고 할 때, 반복문은 최대 n번 반복할 수 있다. 이것의 시간 복잡도는 (n)
  • 배열의 값을 계산하여 target을 비교하는 연산은 상수 시간이 걸린다. 이것의 시간 복잡도는 O(1)
  • 따라서 총 시간 복잡도는 O(n) + O(1) = O(n)이 된다.

• 공간 복잡도

  • 변수는 상수형 데이터만 가지고 있기 떄문에 O(1)의 공간 복잡도를 가진다.

회고

• 다음과 같은 점수를 기록했다.
  

• 더 나은 복잡도를 가지는 방법은 없지만 공간을 아끼기 위해 다음과 같은 방법으로 개선할 수 있었다.

  • 결과 배열에 아무 값을 넣는게 아니라 startIndex, endIndex 넣기.
  • 배열의 값을 더하고 빼며 위치 찾기