[leetcode] two-sum

 

https://leetcode.com/problems/two-sum/description/

Two Sum - LeetCode

 

[문제]

정수의 배열과 목표 합이 주어졌을 때, 배열에 있는 두 숫자의 인덱스가 주어진 목표에 합산되도록 반환합니다.

각 입력에는 정확히 하나의 해가 있다고 가정할 수 있으며, 같은 요소를 두 번 사용할 수 없습니다.
어떤 순서로든 답을 반환할 수 있습니다.

예제 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

예제 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

예제 3:

Input: nums = [3,3], target = 6
Output: [0,1]

 

제약조건:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 답은 오직 하나만 존재합니다.

 

Follow-up: 시간 복잡도를 O(n2) 미만인 알고리즘으로 생각해낼 수 있나요?

 

 

[해답]

먼저 문제 문장을 이해해 봅니다. 여기에는 정수 요소의 배열과 목표 합이 주어집니다. 해야 할 일은 이 배열에 있는 두 요소의 인덱스를 반환하는 알고리즘을 작성하여 이 두 요소를 더하면 주어진 목표 합계와 같아야 하는 알고리즘을 작성하는 것입니다.

예를 들어, 예제 1에서 [7,2,13,11]은 주어진 배열이고 주어진 목표 합은 9입니다. 주어진 배열을 살펴보면 목표 합계 9에 더하는 쌍은 (7,2) 즉, 7+2 = 9입니다. 따라서 알고리즘은 주어진 배열에서 각각 요소 7과 2의 인덱스이므로 [0,1]을 반환해야 합니다.

마찬가지로 예제 2의 배열 [7,3,5]의 출력은 [1,2]인데, 이는 각각 요소 3과 5의 값이 목표 합 8이 되기 때문입니다.

참고: 이러한 쌍이 여러 개 있는 경우 왼쪽에서 찾은 첫 번째 쌍의 인덱스를 반환해야 합니다.

문제 문장에 인덱스를 어떤 순서로든 반환할 수 있다고 명시되어 있는데, 이는 무엇을 의미할까요? 예제 1을 통해 이를 이해해 보겠습니다. 이 예제의 출력은 [0,1]이므로 문제 진술에서 인덱스를 어떤 순서로든 반환할 수 있다는 말은 [0,1] 또는 [1,0]을 출력으로 반환할 수 있다는 의미이며, 둘 다 올바른 것으로 간주됩니다. 예제 2에서도 마찬가지로 [1,2] 또는 [2,1]을 반환할 수 있습니다.

 

 

접근 1: Brute Force

이 문제에 대한 간단한 해결책은 주어진 배열에 존재하는 모든 가능한 쌍을 확인하는 것입니다.

주어진 입력 배열의 개수에 대해 다음 단계를 수행해야 합니다:
  1. 두 개의 루프를 실행하여 주어진 배열의 모든 조합을 확인합니다.

  2. 특정 인덱스에서 외부 루프를 고정하고 내부 루프를 이동하여 가능한 모든 쌍을 얻습니다. 외부 루프는 i=0에서 i=n-2까지 실행되고 내부 루프는 j=i+1에서 j=n-1까지 실행됩니다.
  3. 내부 루프의 각 반복에서 외부 루프와 내부 루프 인덱스로 표시되는 숫자가 목표 합계에 합산되는지 확인합니다.
  4. nums[outerLoopIndex] + nums[innerLoopIndex]가 목표와 같으면 {outerLoopIndex, innerLoopIndex}를 결과로 반환합니다. 그렇지 않으면 반복을 계속하여 다음 쌍을 확인합니다.
  5. 주어진 목표에 합산되는 조합을 찾을 때까지 위의 단계를 반복합니다.

예를 들어 배열 [7,2,13,11]과 목표 합계 24의 경우, 외부 루프를 인덱스 i=0, 즉 요소 7에 고정하고 내부 루프의 가능한 모든 값, 즉 인덱스 1부터 3까지, 즉 j=i+1에서 j=n-1까지로 확인합니다. 따라서 외부 루프의 첫 번째 반복에서 (7,2) (7,13) 및 (7,11) 요소 쌍을 확인하게 됩니다. 이제 외부 루프 인덱스 i를 1씩 증가시키고 내부 루프의 인덱스 2에서 3(i+1에서 n-1)으로 확인합니다. 필요한 답을 찾을 때까지 이 과정을 반복합니다.

참고: 여기서 n은 배열의 크기입니다.

 

Code: Go

func TwoSum(nums []int, target int) []int {
	n := len(nums)
	for i := 0; i < n-1; i++ {
		for j := i + 1; j < n; j++ {
			if nums[i]+nums[j] == target {
				return []int{i, j}
			}
		}
	}
	return []int{}
}

최악의 경우, 이 알고리즘의 런타임 복잡도는 O(n^2)입니다. 필요한 조합이 루프에서 확인해야 하는 마지막 조합일 때 발생합니다.


복잡도 분석

• 시간 복잡도: O(n^2)
• 공간 복잡도: O(1)

 

접근 2: Hashmap 사용

이 문제를 선형 시간 내에 해결할 방법이 있습니다. 해결 아이디어는 해시맵을 사용하여 이미 방문한 요소의 인덱스를 저장하는 것입니다. 해시맵 "key"는 주어진 입력 배열의 번호입니다(각 요소를 방문할 때 해시맵에 이 번호를 추가합니다). 해시맵 "value"는 해시맵 키로 표시되는 배열의 숫자 인덱스입니다.

주어진 입력 배열에 대해 이 알고리즘은 다음 단계를 수행합니다:

  1. 정수 데이터 유형을 키와 값으로 받아들이는 해시맵을 생성합니다.

  2. 첫 번째 요소부터 시작하여 주어진 배열의 각 요소를 반복합니다.
  3. 각 반복에서 필요한 숫자(필요한 숫자 = 목표 합계 - 현재 숫자)가 해시맵에 있는지 확인합니다.
  4. 존재하면 {필요 번호 인덱스, 현재 번호 인덱스}를 결과로 반환합니다.

그렇지 않으면 현재 반복 횟수를 키로, 해당 인덱스를 값으로 해시맵에 추가합니다. 결과를 찾을 때까지 이 과정을 반복합니다.

 

Code: Go

func twoSum(nums []int, target int) []int {
	indexMap := make(map[int]int)
	for currIndex, currNum := range nums {
		if requiredIdx, isPresent := indexMap[target-currNum]; isPresent {
			return []int{requiredIdx, currIndex}
		}
		indexMap[currNum] = currIndex
	}
	return []int{}
}

 

복잡도 분석

• 시간 복잡도: O(n)
• 공간 복잡도: O(n)

최악의 경우 모든 배열 요소를 살펴봐야 하므로 이 솔루션의 런타임 복잡성은 O(n)입니다. 접근 1에서 설명한 것처럼, 최악의 경우는 필요한 조합이 마지막으로 확인해야 할 조합일 때 발생합니다.

또한 배열 요소를 해시맵에 저장하고 최악의 경우 주어진 배열의 모든 값을 해시맵에 저장하게 되므로 필요한 보조 공간은 O(n)입니다.