[Leetcode/JAVA] 01. Two Some

📄 Two Some

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

 

 

문제 분석

정수 배열 nums 의 원소 중 합이 target 인 두 숫자의 인덱스를 반환하는 문제이다.

 

접근 방법

 완전 탐색 을 이용하여  for 문을 통해 합이 target 인 두 원소를 찾을 것이다.

 

정수 배열 nums 의 크기를 $N$이라고 할 때, 시간 복잡도는 $O(N^{2})$이다.

$N$은 최대 $10^{4}$이므로 최대 수행 횟수는 $10^{8}$이고, 따라서 시간 초과에 걸리지 않는다.

 

코드 설계

# 결과를 저장할 배열 result 를 선언한다.

# 이중 for 문을 돌며 배열 nums 에서 두 수를 선택하고, 두 수의 합이 target과 같으면 숫자의 인덱스를 반환한다.

 

코드 구현

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];

        for(int i=0; i<nums.length; i++) {
            for(int j=i+1; j<nums.length; j++) {
                if(nums[i] + nums[j] == target) {
                    result[0] = i;
                    result[1] = j;
                }
            }
        }

        return result;
    }
}

 

---

 

접근 방법

 투 포인터 를 이용하여 합이 target 인 두 원소를 찾을 것이다.

배열을 정렬한 후, 가장 큰 값과 가장 작은 값을 선택한다.

합이 target 보다 작은 경우, 가장 작은 값을 오른쪽으로 이동하면 전체 합이 커지므로 target 값에 더 가까워진다.

합이 target 보다 큰 경우, 가장 큰 값을 왼쪽으로 이동하면 전체 합이 작아지므로 target 값에 더 가까워진다.

 

배열 정렬에 $O(nlogn)$, 합이 tartget이 되는 두 수를 구하는데 $O(n)$가 소요되어 시간복잡도는 $O(nlogn)$이다.

코드 설계

# 결과를 저장할 배열 result 를 선언한다.

# 배열을 그대로 정렬해버리면 기존 인덱스를 알 수 없으므로 기존 인덱스 정보를 따로 저장해주어야 한다.

# 2차원 배열을 생성하여 arr[i][0] 에는 숫자를 arr[i][1] 에는 그 숫자의 원래 인덱스를 저장한다.

# 배열을 오름차순으로 정렬한다.

# 왼쪽 포인터를 l, 오른쪽 포인터를 r 이라고 할 때 l < r 을 만족하는 동안 아래 내용을 반복한다.

# arr[l][0] + arr[r][0] > tartget 이면 r 의 값을 1 감소시키고, arr[l][0] + arr[r][0] < tartget 이면 l 의 값을 1 증가시킨다.

# arr[l][0]+ arr[r][0] = tartget 을 만족하면 두 숫자의 인덱스값인 arr[l][1] 와 arr[r][1] 을 반환하고 while문을 멈춘다.

 

※  반복문 멈추기

while 문 사용할 때, break 문 사용하거나 정답을 만나면 해당 값을 return 해주어야 한다.
그러지 않으면, 정답을 만나도 조건을 만족하지 않을 때 까지 반복되어 시간 초과 문제가 발생한다.

코드 구현

import java.util.Arrays;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        int[][] arr = new int[nums.length][2];

        for(int i=0; i<nums.length; i++) {
            arr[i][0] = nums[i];
            arr[i][1] = i;
        }

        Arrays.sort(arr, (a, b) -> {
            return a[0] - b[0];
        });

        int l = 0;
        int r = nums.length - 1;

        while(l < r) {
            if(arr[l][0] + arr[r][0] > target) {
                r--;
            } else if(arr[l][0] + arr[r][0] < target) {
                l++;
            } else {
                result[0] = arr[l][1];
                result[1] = arr[r][1];
                break;
            }
        }

        return result;
    }
}

 

---

 

접근 방법

 해시 테이블 을 이용하여 합이 target 인 두 원소를 찾을 것이다.

두 수의 합 $a + b = target$ 은 $a = target - b$ 로 변형이 가능하므로 a와 target 값을 통해 b를 구할 수 있다.

코드 설계

# 결과를 저장할 배열 result 를 선언한다.

# 숫자를 key, 숫자의 인덱스를 value로 하는 해시 테이블을 생성한다.

# for 문을 활용해 배열을 순회하며 숫자 b 가 해시 테이블에 존재하는지 확인한다.

# 존재한다면 두 숫자의 인덱스를 반환하고, 존재하지 않는다면 해시테이블에 숫자와 인덱스를 추가한다.

 

코드 구현

import java.util.Arrays;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        Map<Integer, Integer> table = new HashMap<>();

        for(int i=0; i<nums.length; i++) {
            int a = nums[i];
            int b = target - a;

            if(table.containsKey(b)) {
                result[0] = table.get(b);
                result[1] = i;
            }
            table.put(a, i);
        }

        return result;
    }
}

 

동작 과정

nums = [3, 2, 4]  ,  target = 6 인 상황을 살펴보자.

 

( i = 0 )

int a = nums[i];                         // a = 3
int b = target - a;                      // b = 3

if(table.containsKey(b)) {               // table = {} : b 값 없음
    result[0] = table.get(b);
    result[1] = i;
    break;
}

table.put(a, i);                         // table = { (3-0) }

 

( i = 1 )

int a = nums[i];                         // a = 2
int b = target - a;                      // b = 4

if(table.containsKey(b)) {               // table = { (3-0) } : b 값 없음
    result[0] = table.get(b);
    result[1] = i;
    break;
}

table.put(a, i);                         // table = { (3-0), (2-1) }

 

( i = 2)

int a = nums[i];                         // a = 4
int b = target - a;                      // b = 2

if(table.containsKey(b)) {               // table = { (3-0), (2-1) } : b 값 있음
    result[0] = table.get(b);            // result[0] = 1
    result[1] = i;                       // result[1] = 2
    break;
}