[Java] 1. Two Sum

문제 파악

정수 배열 nums 가 주어진다.

 

배열의 두 원소를 더했을 때, target이 되는 값의 인덱스를 반환해야한다.

 

답은 정확히 1개 존재한다.

 

---

풀이

 

1️⃣ HashMap 을 이용한 풀이

💡 떠오른 Idea

각 값을 key 로, 인덱스 값을 value 로 저장하는 map을 정의한다.

nums 배열을 순회하면서 target-nums[i] 가 map 에 존재하는지 확인하고, 존재한다면 답으로 반환한다.

 

import java.util.*;
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            int search = target-nums[i];
            if(map.containsKey(search)){
                return new int[]{i,map.get(search)};
            }
            map.put(nums[i],i);
        }
        return new int[]{};
    }
}

 

결과

 

 

2️⃣ 투 포인터 풀이

💡 떠오른 Idea

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/?envType=study-plan-v2&envId=top-interview-150

예전에 이 문제와 유사한 문제를 풀었던 경험이 있었다.

투 포인터 방식으로, 더했을 때 합이 target 이 되는 위치를 탐색한다.

단, 이 문제에서 요구하는 인덱스는 정렬하기 전 인덱스이므로

정렬하기 전 인덱스를 보관하기 위해 배열로 값과 인덱스를 보관하여, 정답 제출 시 반환하였다.

 

class Solution {
  public int[] twoSum(int[] nums, int target) {
        int N = nums.length;
        int[][] nodes = new int[N][2];
        for (int i = 0; i < N; i++) {
            nodes[i] = new int[]{nums[i], i};
        }

        Arrays.sort(nodes, (a, b) -> a[0] - b[0]);

        int left = 0, right = nodes.length - 1;
        while (left < right) {
            int sum = nodes[left][0] + nodes[right][0];
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                break;
            }
        }

        return new int[]{nodes[left][1], nodes[right][1]};
    }
}

 

결과

이 문제에서 요구했던 것은, Hash 방식 이었기 때문에 속도는 많이 느려졌다.

 

 

---

📖 회고

 

[Java] 167. Two Sum II - Input Array Is Sorted

 

이 문제를 이전에 풀었었는데, Hash를 이용해서 풀 생각은 당시에 하지 못했었다.

 

그래서 다시 이번 문제와 같은, Hash 방식으로 풀어보니 통과도 하였다.

 

당시에는 몰랐지만, 이제부터라도 이런 문제에서 여러 접근법이 있다는 것을 알게 되었으니 잘 기억하고 있어야겠다.