백준 1253번 좋다 python

현재 선택한 값을 만들 수 있는 두 수를 배열에서 찾아야한다.

만약 없다면 -1

있으면 배열에서 있는 개수만큼 찾아서 반환

 

투 포인터로 해결 가능한 문제이다.

leftIndex(배열 왼쪽 끝, 0), rightIndex(오른쪽 끝, len(arr)-1 ) 을 초기값으로 두고

특정 조건에 따라 leftIndex를 +1 오른쪽, rightIndex를 -1 한다.

조건에따라 현재 선택한 값을 만들 수 있는 두 수를 찾으면 count+=1

 

시간복잡도는 

입력 배열 전체를 체크해야하므로 O(N)

입력값 하나당 left~right 까지 체크 O(N)

O(N^2)

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().strip().split(' ')))
arr.sort()
count = 0

for i in range(len(arr)):
    left = 0
    right = len(arr)-1
    while left < right:
        if left == i:
            left += 1
            continue
        if right == i:
            right -= 1
            continue
        sumValue = arr[left]+arr[right]
        # print(sumValue, left, right, arr[left], arr[right])
        if sumValue == arr[i]:
            count += 1
            break
        elif sumValue > arr[i]:
            right -= 1
        else:
            left += 1
print(count)