두 수의 합 문제

두 수의 합 문제

문제

정수 수열 안에서 수열의 원소 두 개의 합이 target값이 되는 경우를 찾고 싶습니다.

매개변수 nums에 길이가 n인 수열이 주어지고, 매개변수 target에 자연수 값이 주어지면 이 수열안에서 두 개의 원소의 합이 정수 target값이 되는 두 원소를 구해 배열에 오름차순으로 담아 반환합니다.

두 개의 원소의 합이 target값이 되는 경우는 오직 한가지 뿐인 입력만 주어집니다. 한 원소를 두 번 더하는 것은 안됩니다. nums의 각 원소는 유일값입니다.

답이 없을 경우 [0, 0]을 반환합니다.

풀이

def solution(nums: list[list[int]], target: int) -> list[int]:
    nums.sort()
    lt = 0
    rt = len(nums) - 1
    result = [0, 0]
    while lt < rt:
        if nums[lt] + nums[rt] > target:
            if nums[lt] > nums[rt]:
                lt += 1
            else:
                rt -= 1
        if nums[lt] + nums[rt] < target:
            if nums[lt] > nums[rt]:
                rt -= 1
            else:
                lt += 1
        if nums[lt] + nums[rt] == target:
            result = sorted([nums[lt], nums[rt]])
            break
    return result

사실 원래 강의에서 의도한 것은 중첩 의문문을 사용하여 O(n^2)으로 푸는것이였는데, 그건 너무 쉬우니까 좀 더 효율적인 방법을 생각해보았다.

위의 문제는 Two-pointer를 이용해서 풀었다. 우선 리스트를 정렬하고, 만일 Left pointer와 Right pointer의 합이 target보다 크면 큰 쪽의 인덱스를 옮긴다.

반대로 두 수의 합이 target보다 작을 경우에는 큰 쪽의 인덱스를 옮긴다. 이런식으로 반복문을 돌면서 두 수의 합이 일치할 때를 찾는다.

이렇게 하면 O(nlogn)이 나올것으로 생각된다…

느낀점

파이썬이 확실히 코테풀기에는 편하구나 싶어서 앞으로는 파이썬으로 코테를 공부할 생각이다. 마침 Django를 공부중이기도 하고…