두수의 합 구하기
오늘 풀어 볼 문제는 "두 수의 합 구하기" 이다.
(link : leetcode.com/problems/two-sum/ )
leet code > Problems의 가장 첫 번째 문제이기 때문에 많이들 풀어봤을꺼라 생각한다.
그럼 바로 시작해보자.
간단하게 문제에 대해 설명하자면 target 숫자와 숫자가 담긴 배열이 주어졌을때, 배열의 두개의 숫자의 합이 target 이 되는 두 수의 위치를 구하는 문제이다.
예를 들면, target이 9이고, 숫자 배열이 [1,2,3,4,5] 일 때, 정답은 [3,4] 가 될 것이다.
단, target이 될 수 있는 경우의 수는 오직 한가지라 했으니 중복 case에 대해선 고려 하지 않아도 된다.
문제 풀이 방법은 다음과 같이 풀었다.
[0] 배열의 원소값을 key로, 위치값을 value로 저장할 Map(혹은 Dictionary)을 준비한다.
[1] 배열의 원소를 순차적으로 확인한다.
[2] 그 후 target 값에서 해당 원소의 값을 뺀다. 왜냐하면 target에서 해당 원소 값을 뺀 값이 배열에 존재한다면, 해당 원소의 위치와 뺀 값의 위치가 정답이기 때문이다.
이 때, 해당 원소의 값이 배열에 있는지 여부를 파악하기 배열을 전체 검색을 하는 것이 아닌 Map을 사용해, O(1)의 수행 시간으로 있는지 여부를 판단하다.
[3-1] 만약 Map에 target에서 해당 원소의 값을 뺀 값이 존재하지 않는다면, 해당 원소를 Map에 저장한다. 이 이유는 뒤이어 이어지는 아직 확인 하지 않은 원소들 중 해당 원소와 짝이 될 수 있는 원소가 있을수도 있기 때문이다.
이 때, Map에는 해당 원소의 값을 key로, 해당 원소의 위치값을 value로 저장한다.
[3-2] 만약 Map에 target에서 해당 원소의 값을 뺀 값이 존재한다면, 해당 원소의 위치값과 Map에 존재하는 value값이 정답이 된다.
▶ 이 문제의 핵심은, 하나의 원소의 짝이 될 수 있는, 즉 해당 원소와 더해서 target 값이 될 수 있는 원소가 배열에 존재하는지를 찾는 것이 핵심 이였다. 이 때, 하나의 원소의 짝을 찾기 위해 배열의 전체를 찾아야 한다면, 수행 시간은 O(N^2)이 될 것이다.
이러한 수행시간을 Map을 통해 줄이는 것이 관건인 문제다.
자세한 코드는 github와 사진으로 남긴다.
package com.algoFactory.leetcode;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/**
* User: Minwoo Kang
* Date: 2020/10/27
* Time: 11:32 PM
* Link: https://leetcode.com/problems/two-sum/
*/
public class Two_sum {
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
int target = 9;
int[] ints = twoSum(nums, target);
assert ints[0] == 0;
assert ints[1] == 1;
System.out.println(Arrays.toString(ints));
}
public static int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
int targetMinusNum = target - num;
if (map.containsKey(targetMinusNum)) { //만약 target에서 현재 원소를 뺀 값이 존재한다면,
//해당 원소의 위치값과 현재 원소의 위치값이 정답이다.
return new int[]{i, map.get(targetMinusNum)};
}
map.put(num, i);
}
return new int[2];
}
}