[Programmers] twosum

문제 파악

배열의 값 중 2개의 값을 선택하여 결과값을 구한다.

접근 방법

1. 정렬 + 투포인트

1. 배열을 정렬한다.
2. 배열 끝과 처음에 포인트를 설정한다 3-1) 두 포인트의 값이 원하는 값 보다 크면 배열 끝 포인트를 뒤로 옮긴다(an-1이 an보다 작기때문) 3-2) 두 포인트의 값이 원하는 값 보다 작으면 배열 앞 포인트를 앞으로 옮긴다(an이 an+1보다 크기때문)

1. HashMap

1. HashMap 객체를 만든다
2. 배열을 순회하면서 (원하는값 - 배열값)의 결과값이 HasmMap에 존재하는지 containKeys()를 통해 확인한다.
3. 존재하지 않으면 HashMap에 배열의 값을 넣는다
4. 존재하면 배열의 값과 HashMap의 값을 출력한다.

코드 구현

 

/*투포이터*/
import java.util.*; //나중에 사용을 위해 명시

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //✅ 숫자와 숫자의 원래 인덱스를 저장하는 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, (o1, o2) -> {
            return o1[0] - o2[0];
        });

        //✅ 첫 번째 인덱스와 마지막 인덱스를 각각 가리키는 두 포인터를 생성한다.
        int l = 0, r = nums.length - 1;
        //✅ 왼쪽 포인터가 오른쪽 포인터보다 작을 동안 반복한다.
        while (l < r) {
            //✅ 합이 target보다 크면 오른쪽 포인터를 왼쪽으로 한칸 옮긴다.
            if (arr[l][0] + arr[r][0] > target) 
                r -= 1;
            //✅ 합이 target보다 작으면 왼쪽 포인터를 오른쪽으로 한칸 옮긴다.
						else if (arr[l][0] + arr[r][0] < target) 
                l += 1;
            //✅ 만약 두 포인터가 가리키는 숫자의 합이 target과 같으면 결과 출력한다.
						else 
                return new int[]{ arr[l][1], arr[r][1] };
        }
        return new int[]{ -1, -1 };
    }
}

 

/*HashMap*/

class Solution {
    public int[] twoSum(int[] nums, int target) { 
        //✅ 숫자와 숫자의 인덱스를 키, 밸류로 하는 빈 해시테이블을 만든다.
        Map<Integer, Integer> memo = new HashMap<>();
        //✅ 숫자들을 순회한다.
        for (int i = 0; i < nums.length; i++) {
		        //✅ 목표값을 만들기 위한 나머지 숫자를 구한다.
            int needed = target - nums[i];
		        //✅ 나머지 숫자가 해시테이블에 존재하면 그 수의 인덱스와 현재 인덱스를 반환한다.
            if (memo.containsKey(needed)) {
                return new int[] {memo.get(needed), i};
            }
		        //✅ 아니라면 해시테이블에 숫자와 인덱스를 추가한다.
            memo.put(nums[i], i);
        }
        return new int[] {-1, -1};
    }
}

 

 

알게된 점

• 합을 구하는 완전 탐색인 경우 포인터를 2개 잡아서 탐색하는 것이 완전 탐색보다 더 효율적으로 탐색할 수 있다.