[자바 알고리즘 인터뷰] 7장 배열 (1) 두 수의 합

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

 

- 덧셈하여 타깃을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라 

 

풀이 1) 브루트 포스로 계산 

 

- 배열을 두 번 반복하면서 모든 조합을 더해서 일일이 확인해보는 무차별 대입 방식인 브루트 포스(Brute-Force)로 풀이 

 

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //입력값 배열을 처음부터 순회
        for(int i=0; i<nums.length; i++)
        {
            //입력값 배열을 그 다음부터 순회
            for(int j=i+1; j<nums.length; j++)
            {
                //두 값의 합을 비교해 target과 일치하는 경우 정답으로 리턴
                if(nums[i]+nums[j] == target)
                {
                    return new int[]{i,j};
                }
            }
        }

        return null;
        
    }
}

 

실행 시간 : 90밀리초 

 

 

풀이 2) 첫 번째 수를 뺀 결과 키 조회 

 

- 비교나 탐색 대신 한 번에 정답을 찾을 수 있는 방식

- target 변수에서 첫 번째 수를 빼면 두 번째 수를 바로 알아낼 수 있다. 

- 두 번째 수를 키로 하고 기존의 인덱스는 값으로 바꿔서 맵으로 저장해두면, 나중에 두 번째수를 키로 조회해서 정답을 즉시 찾아낼 수 있다. 

- 이제 target에서 첫 번째 수를 뺀 결과를 키로 조회해보면 두 번째 수의 인덱스를 조회할 수 있다. 

 

- 주의해야 할 부분은 현재 인덱스를 정답으로 착각할 수 있다는 점이다. 

ex) 배열이 [3,2,4]이고 target이 6인 경우 numsMap.get(3)은 0이 되고, 이렇게 되면 [0,0]이 마치 정답인 것처럼 착각할 수 있다. 

 

import java.util.*;

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

        //키와 값을 바꿔서 맵으로 저장
        for(int i=0; i<nums.length; i++)
        {
            numsMap.put(nums[i],i);
        }

        //target에서 첫 번째 수를 뺀 결과를 키로 조회하고 현재 인덱스가 아닌 경우 정답으로 리턴 
        for(int i=0; i<nums.length; i++)
        {
            if(numsMap.containsKey(target-nums[i]) && i!=numsMap.get(target - nums[i]))
            {
                return new int[] {i, numsMap.get(target-nums[i])};
            }
        }

        //항상 정답이 존재하므로 널이 리턴되는 경우는 없다. 
        return null;

    }
}

 

실행시간 : 11밀리초 

 

 

풀이 3) 조회 구조 개선 

 

- 맵 저장과 조회를 2개의 for문으로 각각 처리했던 방식을 좀 더 개선해 이번에는 하나의 for로 합쳐서 처리 

- 이 경우 전체를 다 저장할 필요 없이 정답을 찾으면 함수를 바로 빠져나올 수 있다. 

 

import java.util.*;

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

        //하나의 for 반복으로 통합
        for(int i=0; i<nums.length; i++)
        {
            //target에서 num을 뺀 값이 있으면 정답으로 리턴
            if(numsMap.containsKey(target-nums[i])) {
                return new int[]{numsMap.get(target-nums[i]),i};
            }
            //정답이 아니므로 다음번 비교를 위해 인덱스를 맵에 저장
            numsMap.put(nums[i], i);
        }

        //항상 정답이 존재하므로 널이 리턴되는 경우는 없다. 
        return null;

    }
}

 

실행시간: 6밀리초 

 

 

풀이 4) 투 포인터 이용 

 

- 투 포인터란 왼쪽 포인터와 오른쪽 포인터의 합이 타깃보다 크다면 오른쪽 포인터를 왼쪽으로, 왼쪽 포인터를 오른쪽으로 옮기면서 값을 조정하는 방식 

 

import java.util.*;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while(left != right) {
            //합이 target보다 작다면 왼쪽 포인터를 오른쪽으로 이동
            if(nums[left]+nums[right] < target){
                left+=1;
            //합이 target보다 크면 오른쪽 포인터를 왼쪽으로 이동
            }else if(nums[left] + nums[right] >target) {
                right -=1;
            }else {
                return new int[] {left, right};
            }
        }
        //항상 정답이 존재하므로 널이 리턴되는 경우는 없다. 
        return null;

    }
}

 

- 투 포인터는 주로 정렬된 입력값을 대상을 하는데, nums는 정렬된 상태가 아니기 때문에 투포인터로 풀이 불가