[Leetcode] 15. 3Sum (In Python)

간략한 코드들은 github.com/Eastar-DS/Python 의 Leetcode 폴더에도 있습니다

Eastar-DS/Python

 

Runtime: 540 ms, faster than 96.29% of Python online submissions for 3Sum.

Memory Usage: 17.4 MB, less than 16.39% of Python online submissions for 3Sum.

런타임이 말도안되게 길어서 글을쓰면서 다시넣어봤는데 문제자체가 런타임이 긴문제였다. 

 

주어진 array에서 세 수의 합이 0이되는 경우가 있는지 찾아내는 문제.

 

워낙 아는게 없어서 처음에 코드를 작성할때는 sort를 하지않고 풀어보려다가 파이썬은 nums = sorted(nums) 라는 간단한 명령어로 해결이 된다는걸 배웠다.

 

nums를 sorting하고(숫자들이 오름차순) nums의 원소 i를 기준으로 i의 오른쪽원소(left로 정의), nums의 끝원소(right)를 첫시작으로 

  1) 세 수의 합이 0보다 작으면 left를 한칸 오른쪽으로 이동시킨다

  2) 세 수의 합이 0보다 크면 right를 한칸 왼쪽으로 이동시킨다 

  3) 세 수의 합이 0이면 리스트에 append해주고 다른 답을 찾기위해 left가 다른수가 되는 순간까지 오른쪽으로 한칸씩 이동시킨다(중복을막기위해). right도 마찬가지로 다른수가 되는 순간까지 한칸씩 왼쪽으로 이동시킨다.

 

 

문제의 출처는 leetcode.com/problems/3sum/입니다.

 

  모르시는게 있으시다면 언제든지 댓글로 질문을 남겨주세요. 저에게 큰 공부가 됩니다. 감사합니다.