LeetCode(릿코드) - Two Sum

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

정수 배열 nums와 정수 target이 input으로 주어질 때, nums안의 2개 element 합이 target과 같은 element의 index를 구하는 문제입니다.

예시는 다음과 같습니다.

Point

1. 문제의 답은 오직 한 가지 쌍이며, 같은 element를 두 번 사용하지 않는다.

 

 

나는 단순하게 풀이를 했다.

Flow 1) 주어진 배열 nums를 정렬한 sortArr에서 합이 target이 되는 element를 탐색

Flow 2) 해당 element의 index를 탐색

class Solution {
    public static int INF = 987654321;
    public int[] twoSum(int[] nums, int target) {
        int[] answer = new int[]{INF, INF};
        int[] sortArr = new int[nums.length];
        /** Flow 1 */
        for(int i=0 ; i<nums.length ; ++i)
            sortArr[i] = nums[i];
            
        System.out.println(Arrays.toString(sortArr));
        int L=0, R=nums.length-1;
        while(true) {
            if(sortArr[L]+sortArr[R] > target) {
                R--;
            }
            else if(sortArr[L]+sortArr[R] < target) {
                L++;
            } 
            else {  // 답을 구한 경우
                break;
            }
        }
        
        /** Flow 2 */
        for(int i=0 ; i<nums.length ; ++i) {
            if(answer[0] == INF && (nums[i] == sortArr[L] || nums[i] == sortArr[R])) {
               answer[0] = i;
            }
            else if(nums[i] == sortArr[L] || nums[i] == sortArr[R]) {
               answer[1] = i;
                break;
            }
        }
        
        return answer;
    }
}

역시 단순하게 풀면 최적화된 풀이와 효율성에서 큰 차이가 난다.

소요시간이 가장 짧은 풀이를 확인해보니 nums 배열의 값을 Map에 저장함과 동시에 target과 차를 통해

쌍이 Map에 존재하는지 확인한다. ( Map.containsKey(target-nums[idx]) 대충 이런 느낌 ) => 완벽한 O(n)