[백준] 1253 좋다 python 풀이

문제

• 난이도: 골드4
• 알고리즘 분류: 자료구조, 정렬, 이분 탐색, 두 포인터
• 요약: n개의 수가 주어졌을 때, 이 중 어떤 수가 다른 두 수의 합으로 표현될 수 있는 수의 개수 출력하기

풀이

예외 처리

타겟과 다른 두 수의 합으로 표현 -> 타겟을 제외한 temp 리스트 생성

시간복잡도

1) Two Pointers 탐색

• 배열 정렬 -> O(N logN)
• 하나의 타겟마다 두 인덱스 변수를 사용해서 O(N) 시간이 소요되기 때문에 모든 원소에 대한 탐색을 진행하면 O(N^2)
• 전체 시간복잡도: O(N^2)

2) Brute Force 탐색

• 배열 정렬 -> O(N logN)
• 하나의 타겟에 대해 조합 가능한 숫자 쌍을 확인하려면 이중 for문 사용 O(N^2), 모든 원소에 대한 탐색을 진행하면 O(N^3)
• 전체 시간복잡도: O(N^3)

코드

n = int(input())
nums = list(map(int, input().split()))

nums.sort()

count = 0

for i in range(n):
    target = nums[i]
    temp = nums[:i] + nums[i+1:]

    left = 0
    right = len(temp) - 1

    while left < right:
        total = temp[left] + temp[right]

        if total == target:
            count += 1
            break

        elif total < target:
            left += 1

        elif total > target:
            right -= 1

print(count)