S01. 릿코드(리트코드) - Two Sum

유투브 강의

: https://www.youtube.com/watch?v=-hGsPMq5wMw&t=557s

소스 코드

: https://leetcode.com/problems/two-sum/discuss/1003158/Java-solution

첫번째 문제 Two Sum 입니다.

문제를 읽어보죠

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

 

Example 1:

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

정수배열인 nums와 정수 target이 주어졌을때 정수배열의 값들 중 두 수의 합이 target이 되는 해당하는 두 수의 배열의 인덱스 값을 리턴하는 문제입니다.

우선 배열이 위의 예시처럼 2,7,11,15가 있다면요, 배열 인덱스는 0부터 시작해서 0,1,2,3이

되겠네요.  0번째 배열 인덱스의 값은 2고, 4번째 배열 인덱스의 값은 15가 되겠습니다.

그럼 두수의 합이 target 예시에서는 9겠네요. 9가 되는 두수는 어떻게 찾을 수 있을까요?

가장 쉬운 방법은 완전 탐색을 이용해 찾는 방법입니다. 완전 탐색이란 모든 경우의 수를 찾는 다는 의미이죠.

첫번째 수는 배열 인덱스 0부터 탐색을 합니다. 그리고 배열의 길이-1 값보다 작을 때까지

탐색합니다. 이 뜻은 배열 마지막 원소 이전까지 탐색한다는 얘기입니다. 

두 수를 찾기 때문에 첫번째 수가 마지막일 수 없습니다. 

for(int i=0;i<length-1;i++){

그리고 리턴값이 두 수의 배열 인덱스이기 때문에 첫번째 수의 배열 인덱스 값을 저장합니다.

ret[0]=i;

그 다음 두번째 수는 첫번째 수의 인덱스 다음부터 탐색합니다. 그리고 배열의 마지막 원소까지 탐색하지요.

for(int j=i+1;j<length;j++){

자 이제 i,j의 해당하는 배열의 값이 target과 같은지 비교합니다.

if(nums[i]+nums[j]==target){

만약 같다면, 리턴값의 두번째로 두번째 수의 배열 인덱스를 저장하고 리턴값을 반환하면 끝입니다.

ret[1]=j;
return ret;

이 문제는 정확히 한개의 솔루션만 있다고 했으므로, 조건에 맞는 답이 나왔으면 바로 리턴하면 됩니다.

그럼 이 방법이 최선일까요?

완전탐색은 말 그대로 모든 경우의 수를 찾아야하기 때문에 시간이 오래 걸립니다.

참고로 코드를 봤을때 시간이 오래 걸릴 것 같은지 체크하는 방법은 for문이 얼마나 중첩이

되었는가를 보면 됩니다. 위의 완전탐색의 경우 2중 for문으로 구현이 되어 있죠.

이제 2중 for문이 아닌 단일 for문으로 이 문제를 해결하는 방법을 알아보겠습니다.

HashMap이라는 것을 활용해 볼텐데요.

HashMap이란 Key, Value를 Pair로 관리해 주는 자료구조 입니다. (자세한건 구글링 ^^)

우선 HashMap의 배열의 요소들을 저장할텐데요. Key는 배열의 값, 그리고, Value는 배열의 인덱스로 저장하겠습니다. 예시에서 첫번째 원소인 2의 경우 Key는 2, Value는 0 , 그리고

세번째 원소인 11의 경우 Key는 11, Value는 2가 되겠네요.

(배열은 0부터 시작하시는 것 아시죠?)

코드는 다음과 같습니다.

Map<Integer, Integer> map = new HashMap<>();
int length = nums.length;
for (int i=0; i <length; i++) {
    map.put(nums[i], i);
}

이제 두수중 첫번째 원소를 찾기 위해 for문을 수행할텐데요.

완전탐색과 마찬가지로 첫번째 인덱스 부터 마지막 원소 이전까지 탐색합니다.

for (int i=0; i<length-1; i++) { 

그리고 두번째 원소의 값이 무엇인지를 확인합니다. 지금 첫번째 원소를 탐색하기 때문에 우리는 첫번째 원소의 값(엄밀히 따지면 후보)를 알고 있죠. target값에서 이것을 빼면 두번째 원소의 값이 무엇인지를 알 수 있습니다.

int other = target - nums[i];

만약 이 두번째 원소 후보가 HashMap에 저장이 되어 있고 그 인덱스가 첫번째 원소의 인덱스가 아니라면(다른 값이라면) 우리는 첫번째, 두번째 원소를 찾게 되는 겁니다.

if (map.containsKey(other) && map.get(other) != i) 

HashMap을 이용한 문제풀이는 단일 for문만을 사용하였기 때문에 완전탐색 풀이보다 속도가 훨씬 빠르답니다. ^^

이해가 되지 않다면 맨위 동영상 확인해 주세요

그냥보는 알고리즘은 계속됩니다~