Leet Code - 167. Two Sum II - Input array is sorted(C++)

예제: Two Sum II - Input array is sorted

문제
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

• Your returned answers (both index1 and index2) are not zero-based.
• You may assume that each input would have exactly one solution and you - - may not use the same element twice.

Example:

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.

풀이

array 안의 두 숫자의 합이 target이 되는 두 인덱스를 리턴하는 문제이다.

2중 for문으로 풀라고 낸 문제는 아닌게 분명하고(혹시 제출해 봤지만 역시나 time limit exceeded 였다.), O(n) 시간 안에 풀 수 있을 것이라는 느낌이 왔다.

이에 필자는 array의 왼쪽, 오른쪽 끝에서의 합(sum)이 target보다 작으면 왼쪽 index를 하나 더해주고, 반대면 오른쪽 index를 하나 빼주면서 sum == target이 될 때 return하는 로직을 코드로 구현했다.

전체적인 소스코드는 아래와 같다.

소스 코드

class Solution {
public:
	vector<int> twoSum(vector<int>& numbers, int target) {
		vector<int> res;
		int left = 0, right = numbers.size() - 1;

		while (left < right) {
			int sum = numbers[left] + numbers[right];
			if (sum == target) {
				res.push_back(left + 1);
				res.push_back(right + 1);
				return res;
			}
			else if (sum < target) {
				left++;
			}
			else {
				right--;
			}
		}

		return res;
	}
};

풀이 후기

별 것 아닌것처럼 생각되기도 하지만, 그동안 leet code로 단련하지 않았다면 빠르게 풀 수 있었을까.. 하는 문제이다. 알고리즘도 재밌지만, 영상처리라던지 다른 것도 하고 싶은 생각이 문득 든다. 하지만 지금은 알고리즘을 많이 할 시기이다.. 힘을 내자!