LeetCode알고리즘 4Sum

오늘은 18번 문제를 풀어보겠습니다.
중간 난이도고 36.5%의 성공률을 보이네요.

 

오늘 주제는 Two Pointers입니다.

n정수들로 구성된 nums배열이 주어지면, 
nums[a], nums[b], nums[c], nums[d]는
a,b,c,d는 0이상 n미만이고
a,b,c,d는 별개이고
nums[a], nums[b], nums[c], nums[d]의 합이 target과 같은 유니크한 quadruplets의 배열을 리턴하세요.
순서는 상관없습니다.

 

예시를 보겠습니다.

1번을 보면 아웃풋으로 나온 각 1차 배열들의 원소를 합치면 타깃이 됩니다.
-2 + -1 + 1 + 2 = 0
-2 + 0 + 0 + 2 = 0
-1 + 0 + 0 + 1 = 0
이렇게 타깃으로 되는 배열을 만들어서 리턴해주면 됩니다.

 

*추가로 아래와 같이 제약 조건들이 있습니다.

 

문제를 풀어보겠습니다.

 

투 포인터로 범위를 파악하기 위해 정렬을 해주었습니다.
그리고 중복 제거를 위해 집합을 만들어줬어요. 
for 루프 i을 기준으로 루프를 돌게 됩니다.
내부 for 루프는 j 에 i+1을 해준 값으로 시작하게 됩니다.
내부에 k,o를 선언하고 i,j인덱스 초과된 범위를 잡게 됩니다.
(k = j + 1) 왼쪽에서 증가해나감
(o = nums.count -1) 오른쪽에서 감소해나감
즉 k,o를 가지고 범위를 좁혀나가며 target비교를 해주는 것입니다.
while문 내에서 k < o가 만족할 때까지 돌면서 nums[a], nums[b], nums[c], nums[d]의 합이 target과 맞으면 answer집합에 삽입을 해주는 것입니다.

class Solution {
    func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {        
        guard nums.count >= 4 else { return [] }
        var answer = Set<[Int]>()

        let nums = nums.sorted()
        
        for i in 0..<nums.count {
            for j in i+1..<nums.count {
                
                var k = j + 1
                var o = nums.count - 1
                
                while(k < o) {
                    let sum = nums[i]+nums[j]+nums[k]+nums[o]

                    if sum == target {
                        answer.insert([nums[i],nums[j],nums[k],nums[o]])
                        k = k + 1
                        o = o - 1
                    } else if sum > target {
                        o = o - 1
                    } else {
                        k = k + 1
                    }
                }
            }
        }
        return Array(answer) 
    }
}

그리고 리턴은 배열로 리턴

 

이렇게 했을 때 결과

는 그닥... 좋지는 않네요.
(투 포인터는 항상 이렇게 풀었는데 개선할 수 있는 부분을 찾아서 개선해보는 노력도 해야겠습니다.)

 

그럼 이만!

 

resource:
https://leetcode.com/problems/4sum/