leetcode-study/3sum/haklee.py at main · 01-binary/leetcode-study

76 lines (68 loc) · 4.43 KB
"""TC: O(n^2), SC: O(n^2)
- 합이 0(즉, 고정값)이 되는 세 수를 찾는 것이 문제.
- 세 수 중 하나가 고정되어 있다면, 그리고 숫자들이 들어있는 리스트가 정렬되어 있다면 투 포인터 사용 가능.
    - 투 포인터 테크닉은 검색하면 많이 나오므로 아주 자세한 설명은 생략하겠다.
    - 이 문제에서는 리스트의 가장 작은 값과 가장 큰 값에 포인터를 둘 것이다.
    - 그리고 이 두 값의 합이
        - 원하는 결과보다 작으면 작은 값의 포인터를 큰 쪽으로 옮기고,
        - 원하는 결과보다 크면 큰 값의 포인터를 작은 쪽으로 옮긴다.
    - 이 과정을 반복하면서 원하는 쌍을 찾는 것이 관건.
- 고정된 숫자를 정렬된 리스트의 가장 작은 값부터 큰 값으로 하나씩 옮겨가면 중복 없이 탐색이 가능하다.
    - 이때 투 포인터를 쓸 구간은 고정된 숫자 뒤에 오는 숫자들로 둔다.
    - 코드를 보는 것이 이해가 더 빠를 것이다..
- 자세한 설명은 TC 분석에서 확인 가능.
- 종합하면 O(n^2).
- nums를 sort하는 과정에서 O(n * log(n))
- 정렬된 nums를 모두 순회.
    - 그리고 각 순회마다 n-1, n-2, ..., 2 크기의 구간에서 투 포인터 사용.
    - 투 포인터를 사용할때 단순 사칙연산 및 비교연산만 사용하므로 O(1).
    - 투 포인터 사용시 매 계산마다 포인터 사이의 거리가 1씩 줄어든다(s가 올라가든 e가 내려가든).
    - (SC) 매 계산마다 최대 한 번 solution을 추가하는 연산을 한다.
    - 그러므로 각 순회마다 C * (n-1), C * (n-2), ..., C * 1의 시간이 들어감.
    - (SC) 비슷하게, 매 순회마다 위와 같은 꼴로 solution 개수가 더해질 수 있다.
    - 종합하면 O(n^2)
from collections import Counter
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 커팅. 어차피 세 쌍의 숫자에 등장할 수 있는 같은 숫자 개수가 최대 3개이므로,
        # 처음 주어진 nums에 같은 숫자가 네 번 이상 등장하면 세 번만 나오도록 바꿔준다.
        # 이 처리를 하면 같은 숫자가 많이 반복되는 케이스에서 시간 개선이 있을 수 있다.
        # Counter 쓰는 데에 O(n), 새로 tmp_nums 리스트를 만드는 데에 O(n)의 시간이 들어가므로
        # 최종적인 시간 복잡도에 영향을 주지는 않는다.
        tmp_nums = []
        for k, v in Counter(nums).items():
            tmp_nums += [k] * min(v, 3)
        # 여기부터가 주된 구현.
        sorted_nums = sorted(tmp_nums)  # TC: O(n * log(n))
        nums_len = len(tmp_nums)
        sol = set()
        for i in range(nums_len):  # TC: O(n)
            if i > 0 and sorted_nums[i] == sorted_nums[i - 1]:
                # 커팅. 고정 값이 이미 한 번 사용되었던 값이면 스킵해도 괜찮다.
                continue
            s, e = i + 1, nums_len - 1
            while s < e:
                # 이 while문 전체에서 TC O(n).
                v = sorted_nums[s] + sorted_nums[e]
                if v == -sorted_nums[i]:
                    # i < s < e 이므로, 이 순서대로 숫자는 정렬된 상태다.
                    # 즉, 같은 값을 사용한 순서만 다른 쌍을 걱정하지 않아도 된다.
                    sol.add((sorted_nums[i], sorted_nums[s], sorted_nums[e]))
                if v < -sorted_nums[i]:
                    # s, e의 두 값을 더한 것이 원하는 값보다 작으면, 작은 쪽에 있는 포인터를
                    # 더 큰 숫자가 있는 쪽으로 옮기면 된다.
                    # 여기서도 중복 값 커팅을 하려면 할 수 있겠지만, 이 커팅을 안 하려고
                    # 맨 앞에서 같은 숫자들을 미리 최대한 제거해두었다.
                else:
                    # s, e의 두 값을 더한 것이 원하는 값보다 크면, 큰 쪽에 있는 포인터를
                    # 더 작은 숫자가 있는 쪽으로 옮기면 된다.
                    # 여기서도 중복 값 커팅을 하려면 할 수 있겠지만, 이 커팅을 안 하려고
                    # 맨 앞에서 같은 숫자들을 미리 최대한 제거해두었다.
        return sol  # 타입힌트를 따르지 않아도 제출은 된다...
Provide feedback

Saved searches

Use saved searches to filter your results more quickly

FilesExpand file tree

haklee.py

Latest commit

History

haklee.py

File metadata and controls
