배열에서 두 원소의 합 (2Sum)

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장.

 

2Sum

정수 배열과 목표 숫자 가 주어지면 배열의 원소들 중 2 개를 골라 합산하여 목표수를 만들 수 있는지 계산한다. N 개의 원소를 N 번 반복해 답을 구하는 완전 탐색이 가능하지만, O(N^2) 의 시간복잡도를 가지므로 개선된 두 가지 방식으로 풀어본다.

Two pointer

첫 번째는 두 개의 포인터를 사용하는 방법으로 O(N*logN) 에 문제를 해결한다. 정렬된 배열이 필요하므로 N 개의 원소에 대해 N * logN 만큼 연산하고, 정렬된 배열을 한 번 반복하며 합을 찾으므로 N 만큼의 시간이 더 든다.

 

bool twoPointerSolution(const vector<int>& ori, int target) {

	int lo = 0, hi = ori.size() - 1;
	vector<int> arr(ori.begin(), ori.end());
	sort(arr.begin(), arr.end());
    
	while (lo < hi) {
		int cand = arr[lo] + arr[hi];
		if (cand == target) return true;
		else if (cand < target) ++lo;
		else --hi;
	}
    
	return false;
}

HashMap

HashMap 을 이용하면 반복문 한 번으로 답을 찾을 수 있다. 만약 (목표값 - 어떤 원소)의 값이 배열에 있다면 목표값을 만들 수 있다. Hash Map 을 사용하면 차이값을 상수 시간에 찾으므로 반복문 한 번에 정답을 찾는다. 시간 복잡도는 O(N).

 

bool hashSolution(const vector<int>& ori, int target) {

	unordered_map<int,int> m;

	for (int i = 0; i < ori.size(); ++i) {
		if (m.find(target - ori[i]) != m.end()) return true;
		// key: i 번째 원소, value: i 
		m[ori[i]] = i;
	}

	return false;
}