Leetcode) 3Sum

Top Interview Questions
Medium Collection

Link of Problem

LEVEL : 🌕 🌕 🌕 🌑 🌑 (중)

---

Array에서 Easy Collection은 끝났기 때문에 Medium Collection으로 넘어왔습니다.!

역시나 어려웠고, 쉽게 풀리지 않았습니다.🥲
첫 문제부터 저는 1시간만에 Solution를 찾아 봤네요.. 열심히 해야겠습니다.

3Sum은 배열안에 있는 숫자들 중에 3개 숫자의 합이 0이 되는 조합을 찾아서 배열 형태로 배열에 넣는 문제였습니다.

처음에 문제를 풀었을 때, 되겠다 싶었는데. 나타날 다양한 케이스를 고려하지 않아서 각 케이스에서 Wrong이 뜰 때마다 보수공사를 했습니다.. 결론적으로 이 코드는 못 쓰겠다 싶어서 다른 방식들을 찾아봤고 결과적으로 좋은 코드를 찾을 수 있었습니다.

정렬하는 방식들을 정말 많이 공부해야겠어요...🥲

1️⃣ 번째 방법

해당 방식은 Wrong Answer만 나왔습니다.

문제를 보자마자 정렬을 시킨 다음, 앞 숫자부터 2개씩 묶어서 뒤에 숫자와 합이 0이 되는지 봐야지. 라고 생각했지만. 너무 많은 케이스를 고려 안했습니다..🥲

당연히 nums안에 있는 케이스가 3개 미만이라면 3개의 sum를 찾을 수 없기 때문에 빈 배열을 return했고, nums를 sorted한 값들이 들어있는 sortedNums의 가장 첫 번째값이 0보다 크다면 아무리 세 값을 더해도 0이 나올 일이 없다는 뜻이기에 빈 배열을 return해줬습니다.

그리고 아래 코드에서 볼 수 있듯이 두 값을 묶은 다음(0 이하인 두 값), 0 이상인 한 값과 더 해서 sum이 나오면 answers에다가 넣어줬습니다.

하지만 문제가 많더라구요..
먼저 중복이 생기는 문제가 나와서 return할 때 Set으로 감싸주는 일을 했어요.
그 다음으로 생긴 문제가 양의 정수 두 개가 음의 정수 한 개와 더해졌을 때 0이 되는 케이스가 있다는 겁니다.
이 케이스를 다루려면 완전히 코드를 새로 짜는 게 낫다는 결론이 나서 다른 코드를 찾아봤습니다.

func threeSum(_ nums: [Int]) -> [[Int]] {
    guard nums.count >= 3 else { return [] }
    
    let sortedNums = nums.sorted()
    guard sortedNums[0] <= 0 else { return [] }
    
    var answers: [[Int]] = []
    for i in 1..<sortedNums.count where sortedNums[i-1] <= 0 {
        let sum = sortedNums[i] + sortedNums[i-1]
        
        if sum > 0 { continue }
        
        if i+1 > sortedNums.count-1 { break }
        
        for j in (i+1...sortedNums.count-1).reversed() where sortedNums[j] >= 0 {
            if sum + sortedNums[j] == 0 {
                answers.append([sortedNums[i-1], sortedNums[i], sortedNums[j]])
                break
            }
        }
    }
    
    return Array(Set(answers))
}

2️⃣ 번째 방법

결론적으로 답이 된 코드입니다.

일단 세팅하는 코드는 비슷합니다. 다른 점은 풀어가는 방식이죠!
왜 이 생각을 못했지 싶었습니다..

first current last 이 세가지 숫자를 둘 겁니다.
first(i)는 맨 앞에서부터 오는 값,
last(k)는 맨 뒤에서부터 오는 값,
current(j)는 first와 last 사이 값을 찾을 겁니다.

first는 for문을 통해서 차례대로 받아올 것이고,
current는 항상 first+1한 값에서 시작할 겁니다.
last는 맨 뒤(count - 1)에서 시작하면 되겠죠?

중간 중간 sorted[i] == sorted[i-1], sorted[j] == sorted[j-1]인 경우를 넘겨서 중복이 생길 경우들도 없애줄 거예요.

그리고 current가 last보다 작을 때에만 first + current + last의 값을 구하고 그 값이 0이 맞다면 result에 넣을 겁니다.
만약에 sum보다 작다면, current(j)값을 위로 올려서 sum값을 올리겠죠.
반대로 sum보다 크다면, last(k)의 값을 내려서 sum값을 내릴겁니다.

해당 코드는 이러한 과정을 통해서 진행됩니다.

func threeSum(_ nums: [Int]) -> [[Int]] {
    guard nums.count >= 3 else { return [] }
    
    let sorted = nums.sorted()
    var result: [[Int]] = []
    for i in 0..<sorted.count {
        if i != 0, sorted[i] == sorted[i-1] { continue }
        
        var j = i + 1
        var k = sorted.count-1
        
        while j < k {
            let sum = sorted[i] + sorted[j] + sorted[k]
            if sum == 0 {
                result.append([sorted[i], sorted[j], sorted[k]])
                j += 1
                while j < k, sorted[j] == sorted[j-1] {
                    j += 1
                }
            } else if sum < 0 {
                j += 1
            } else {
                k -= 1
            }
        }
    }
    
    return result
}

세 값을 나눠서 진행하기 때문에 위에 코드처럼 2개씩 묶기 때문에 나타나는 문제도 해결되고, 심지어 중복도 나타날 일이 없습니다.
first, last, current를 따로 나눠서 배열 문제를 해결해본 적이 처음이라서 바로 생각하지 못한 거 같습니다. 이제 알게됐으니 열심히 사용해보려구요. 너무 좋네요👍