[파이썬 알고리즘 인터뷰] 배열 - 세수의 합

문제설명

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

예시

 

#입력
nums = [-1, 0, 1, 2, -1, -4]

#출력
[
[-1, 0, 1], 
【-1, -1, 2]
]

 

풀이

앞 뒤로 같은 값이 있을 경우를 대비해 sort() 함수를 사용

중복된 값이 있을수 도 있기 때문에 continue로 건너 뛴다.

세 개의 포인터를 이용하여 각각의 포인터가 이동하면서 i + j + k = 0을 찾아내서 반환을 해준다.

 

 

def three_sum(nums):
    results = []
    nums.sort()
    print(nums)
    # 앞 뒤로 같은 값이 있을 경우를 대비해 sort() 함수를 사용


    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        for j in range(i + 1, len(nums) - 1):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue

            for k in range(j + 1, len(nums)):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue # 중복된 값이 있을수 도 있기 때문에 continue로 건너 뛴다.

                if nums[i] + nums[j] + nums[k] == 0:
                    # 세 개의 포인터를 이용하여 각각의 포인터가 이동하면서 i + j + k = 0을 찾아냄
                    results.append((nums[i], nums[j], nums[k]))

    return results


nums = [-1, 0, 1, 2, -1, -4]
print(three_sum(nums))

출력

/Users/hamyeong-gwan/opt/anaconda3/envs/ptu/bin/python /Users/hamyeong-gwan/Desktop/PYTHON/알고리즘/brute_force_3S.py
[-4, -1, -1, 0, 1, 2]
[(-1, -1, 2), (-1, 0, 1)]

Process finished with exit code 0