[Java] LeetCode(Easy) - 1. Two Sum

문제 풀이

---

배열의 원소를 순회하며 두 수의 합이 target이 되는지 판단하면 되는 간단한 문제이다. 필자는 완전탐색과 HashMap 2가지를 이용해서 풀어보았다.

아이디어 도출 - 완전탐색

완전탐색의 경우 문제 요구사항 그대로 구현하면 된다.

1. nums 배열을 순회하며 자리별로 두 수의 합이 target이 되는 인덱스가 있을 경우 List에 삽입한다.
2. 삽입된 List를 Array로 반환한다.

완전탐색을 할 경우, 시간복잡도가 O(n^2)이기에 비효율적이다.

아이디어 도출 - HashMap

HashMap을 이용하면 완전탐색 풀이에 비교하면 O(n)으로 보다 효율적인 성능을 보여준다.

1. nums 배열을 순회하며 배열의 원소를 key로, 인덱스를 value로 HashMap에 삽입한다.
2. target - 원소 값이 HashMap에 존재한다면, 두 수의 합을 만들 수 있다고 가정하여, target - 원소 값의 인덱스와 현재 원소의 인덱스를 반환한다.

위와 같이 2가지 방식으로 문제를 풀어보았다. 문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

import java.util.*;

public class LeetCode {

    // 완전탐색의 경우 시간복잡도 O(n^2)의 시간이 걸리기에 비효율적이다.
    public int[] twoSum1(int[] nums, int target) {
     
        // 두 수를 담을 List
        List<Integer> list = new ArrayList<>();

        // nums 배열을 순회하면서 두 수의 합이 target이 되는 인덱스를 구한다.
        for(int i=0; i<nums.length; i++) {
            for(int j=0; j<nums.length; j++) {
                if(i != j) {
                    if(nums[i] + nums[j] == target) {
                        list.add(i);
                    }
                }
            }
        }

        // List를 Array로 반환한다.
        return list.stream().mapToInt(Integer::intValue).toArray();

    }

    // 시간복잡도 O(n)으로 풀기 위해 HashMap을 사용한다.
    public int[] twoSum2(int[] nums, int target) {
     
        Map<Integer, Integer> hm = new HashMap<>();
        int[] answer = new int[2];

        for(int i=0; i<nums.length; i++) {
            if(hm.containsKey(target - nums[i])) {
                answer[0] = hm.get(target - nums[i]);
                answer[1] = i;
                break;
                
            }
            hm.put(nums[i], i);
        }

        return answer;

    }

    public static void main(String[] args) {

        LeetCode leetCode = new LeetCode();

        int target = 6;

        // int[] nums = new int[]{2, 7, 11, 15};
        // int[] nums = new int[]{11, 7, 15, 2};
        int[] nums = new int[]{3, 3};
        
        leetCode.twoSum2(nums, target);

    }

}

회고

출처

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.