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

https://leetcode.com/problems/3sum/description/

 

- 배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라 

 

 

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

 

- Arrays.osr(nums)로 정렬

- i.j,k 각각의 포인터가 계속 이동하면서 i+j+k=0을 찾아낸다. 

- 브루트 포스 풀이에는 중복된 값이 있을 수 있으므로 continue로 건너뛰도록 처리 

 

 

import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> results = new LinkedList<>();
        Arrays.sort(nums);

        //브루트 포스 n^3 반복
        for(int i=0; i<nums.length-2; i++) {
            //중복된 값 건너뛰기
            if(i>0 && nums[i] == nums[i-1])
                continue;
            for(int j=i+1; j<nums.length-1; j++){
                //중복된 값 건너뛰기
                if(j>i+1 && nums[j] == nums[j-1])
                    continue;
                for(int k=j+1; k<nums.length; k++) {
                    //중복된 값 건너뛰기
                    if(k>j+1 && nums[k] == nums[k-1])
                        continue;
                    if(nums[i] + nums[j] + nums[k] == 0)
                        results.add(Arrays.asList(nums[i],nums[j], nums[k]));
                }
            }
        }

        return results;
    }
}

 

실행시간: 타임아웃

 

 

풀이 2) 투 포인터로 합 계산 

 

- i의 다음 지점과 마지막 지점을 left, right로 설정하고 간격을 좁혀가면서 sum을 계산 

 

출처 : 자바 알고리즘 인터뷰 with 코틀린 박상길 <책만>

 

- 합 sum이 0보다 작다면 값을 더 키워야 하므로 left를 우측으로 이동하고, 0보다 크다면 값을 더 작게 하기 위해 right를 좌측으로 이동한다. 

- sum이 0이면 정답이므로, 이 경우 결과를 리스트 변수 results에 추가한다. 

- 추가한 다음에는 left, right 양 옆으로 동일한 값이 있을 수 있으므로 같은 정답이 두 번 나오지 않도록 left+=1, right -=1을 반복해서 스킵하도록 처리한다. 

- 마지막으로 left를 한 칸 우측으로, right를 한 칸 좌측으로 더 이동하고 다음으로 넘긴다. 

 

import java.util.*;

class Solution {
    int left,right,sum;
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> results = new LinkedList<>();
        Arrays.sort(nums);

        for(int i=0; i <nums.length-2; i++) {
            //중복된 값 건너뛰기
            if(i>0 && nums[i] == nums[i-1])
                continue;

            //간격을 좁혀가며 합 sum 계산
            left = i+1;
            right = nums.length -1;

            while(left<right) {
                sum = nums[i] + nums[left] + nums[right];

                //합이 0보다 작다면 왼쪽 포인터 이동
                if(sum<0)
                    left+=1;
                //합이 0보다 크다면 오른쪽 포인터 이동
                else if(sum > 0)
                    right -=1;
                else {
                    //합이 0인 경우이므로 정답 처리
                    results.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    //중복된 값 건너뛰기, 이 처리를 하지 않으면 같은 정답이 두 번 나올 수 있다.
                    while(left<right && nums[left] == nums[left+1])
                        left+=1;
                    while(left<right && nums[right] == nums[right-1])
                        right-=1;

                    //정답이 나왔으므로 투 포인터 모두 한 칸씩 이동
                    //합이 0인 상황이므로 양쪽 모두 이동해야 한다. 
                    left+=1;
                    right-=1;
                }

            }
        }

        return results;
    }
}

 

실행시간 : 28 밀리초