APAS 1 - Two Sum

APAS라는 안드로이드 앱에 있는 문제들을 분석하고 이에 대한 제 생각 및 실제 결과를 비교하려고 합니다.

int 배열이 있을 때, 주어진 값을 만들 수 있는 2개의 숫자쌍의 index 위치를 반환하라
동일한 index는 중복하여 사용될 수 없으며 주어진 값을 만들 수 있는 배열 내 숫자쌍은 1개만 존재하는 것으로 가정한다

ex)
입력값 : [2, 7, 11, 15]
주어진 값 : 9

답 : 0, 1

[문제 분석]

• int값이기 때문에 입력값 중 음수가 나올 수 있다
  • 따라서 주어진 입력값 내에서 주어진 값 초과(양수) 또는 미만(음수)의 값을 건너뛸 수 없으며 모든 데이터를 순회해야 한다
• 2개의 데이터만을 사용해 주어진 값을 생성해야 한다.

[내가 생각했던 결과 소스]

void Twosum::doTest(std::vector<int> &inputList, int target) {
	int firstIndex = 0;
	int secondIndex = 0;
	for (unsigned int i = 0; i < inputList.size(); i++) {
		for (unsigned int j = i + 1; j < inputList.size(); j++) {
			if (inputList[i] + inputList[j] == target) {
				firstIndex = i;
				secondIndex = j;
			}
		}
	}

	printf("[%d %d]\n", firstIndex, secondIndex);
}

 

[실제 결과 소스]

void Twosum::doTest(std::vector<int> &inputList, int target) {
	std::map<int, int> inputMap;
	for (unsigned int i = 0; i < inputList.size(); i++) {
		int remain = target - inputList[i];
		if (inputMap.find(remain) != inputMap.end()) {
			printf("[%d %d]\n", inputMap.at(remain), i);
			break;
		}
		inputMap.insert(std::make_pair(inputList[i], i));
	}
}

 

[해설]

• 처음엔 단순하게 생각해서 배열 내 모든 요소를 1회씩 순회하며 동일한 sum을 만드는 두 요소가 있는지를 찾으면 될 줄 알았다
  • 그렇게 해도 동작은 한다
• 하지만 모든 요소를 순회할 경우 : 시간복잡도 O(N^2)로, 좋지 않다
• 실제 결과 소스에서는 '주어진 값 - 현재 내 값'의 데이터가 입력값 중에 있는지를 찾음으로써 모든 요소를 1번만 순회해도 답을 찾음 - 시간복잡도 O(N)