Find triplets with zero sum

https://practice.geeksforgeeks.org/problems/find-triplets-with-zero-sum/1/

요번에 같이 볼 문제는 이거다.

배열에 integer들이 쭈욱 들어 있을때 과연 이 중 3개를 더해서 0이 되는 조합이 있는지 확인하는 문제다. 문제는 간단한데 생각보다 어렵다.

훔.. space 가 O(1)인게 가장 걸린다.

시도1. Brute-force 를 하려면 O(n^3) 이 걸린다.

시도2. 그래서 생각한게 Integer 두개를 골라서 그 둘의 합이 0 되게 하는 세번째 숫자를 모두 저장한다. 필요한 세번째 숫자가 배열에 있다면 True 아니라면 False.

잘하면 O(n^2) 로 세번째 숫자를 구하고, 세번째 숫자를 비교하는것도 O(n^2) 에 해결 할 수 있겠지만 문제는 space가 O(1) 밖에 주어지지 않는다. 또, corner case로 [-4, 2] 같은 것도 True로 반환될 것임으로 예외처리를 하기 위해선 어떤 숫자들을 더했는지 기록해야한다.

시도3. 시도2와 유사하나 세번째 숫자가 배열내에 있는지 확인 여부를 즉각적으로 확인한다.

아이디어는 다음과 같다.

배열을 O(nlogn)으로 오름차순으로 정렬한다.
a, b, c 세 숫자를 골라 합이 0인지 지속적으로 확인할텐데, a < b < c 라는 조건을 만족시키는 a, b, c를 선택한다.
a, b 는 가능한 가장 작은 숫자부터 시작하고 c는 가장 큰 숫자부터 시작한다.
a + b + c 가 0이 되는지 확인한다. 맞다면 return True.
합이 0이 되지 않는다면 a + b 와 c 의 값을 비교해서 a + b 가 커지거나 c 가 작아지게 조절한다.
모두 다 확인해도 0이 되는 조합이 없다면 return False.

class Solution:
    #Function to find triplets with zero sum.    
    def findTriplets(self, arr, n):
        arr.sort()
        for a in range(n):
            c = n - 1
            for b in range(a+1, n):
                if arr[a] + arr[b] > 0 or b >= c: # breaking case
                    break
                
                if arr[a] + arr[b] + arr[c] == 0:
                    return True
                    
                while arr[a] + arr[b] + arr[c] > 0 and c > b:
                    # a + b will monotonically increase
                    # checking against anything larger than current third value is impossible
                    c -= 1
        return False

제출전에 stopping case에 문제가 있단 걸 깨달았다. 굳이 쟤네 합이 양수여야 하나? 답은 노.

제출했더니 역시나 틀렸다.

틀렸던 예제는

6
97 -27 2 -34 61 -39

while문 안에서 a, b, c 를 프린트해보니 다음과 같이 나온다.

[-39, -34, -27, 2, 61, 97] 
0 1 5
0 3 4 
1 2 5 
1 3 4 
2 3 5 
2 3 4 
3 4 5

문제는 (a, b, c) 각각의 인덱스가 (1, 2, 5) 일때 합이 양수 (-34 + -27 + 97) 임을 확인하고나서 c 인덱스를 4로 만든 후 합이 0이 되는지 확인하지 않는다.

그래서 순서를 바꿔서 제출해봤다

그랬더니 성공! 끝.

P.S.) 에디토리얼 찾아보니 아이디어는 비슷한데 timeout 나온다.

전체코드

class Solution:
    #Function to find triplets with zero sum.    
    def findTriplets(self, arr, n):
        arr.sort()
        # print(arr)
        for a in range(n):
            c = n - 1
            for b in range(a+1, n):
                if b >= c: # stopping case, 
                    break
                
                while arr[a] + arr[b] + arr[c] > 0 and c > b:
                    # print(a, b, c)
                    # a + b will monotonically increase
                    # checking against anything larger than current third value is impossible
                    c -= 1
                    
                if arr[a] + arr[b] + arr[c] == 0:
                    # return True
                    return 1
                    
        # return False
        return 0

답글 남기기 응답 취소