백준 1253: 좋다 (파이썬 풀이)

https://www.acmicpc.net/problem/1253

1253번: 좋다

 

시간복잡도 -> 제한시간이 2초이고 N의 개수가 2000입니다. (제한시간 2초면 연산 4천만번 가정)

만약 좋은수 하나를 찾는 알고리즘의 시간복잡도가 N^2 이라면

반복문을 돌리는데 총 N^3의 시간복잡도가 되므로 N^2 알고리즘은 사용할 수 없습니다.

따라서 NlogN의 시간복잡도 알고리즘을 사용해야합니다.

정렬후에 (파이썬 퀵소트 : NlogN)

투 포인터를 이용하면 가능합니다.

 

수를 입력받아 리스트에 저장후

투 포인터 start를 시작 인덱스로, end를 마지막 인덱스로 하여

좋은수가 될때까지 포인터의 범위를 줄여줍니다.

 

중요한 예외사항이 있는데

정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함하면 안됩니다 !!

 

내가 틀렸던 반례 )

11

0 1 2 3 4 5 6 7 8 9 10

 

답 : 8

---

소스코드

# 투 포인터
import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
arr.sort()

cnt = 0
for i in range(n):
    goal = arr[i]
    start = 0
    end = len(arr)-1
    while start < end:
        if arr[start] + arr[end] == goal:
            if start == i:
                start += 1
            elif end == i:
                end -= 1
            else:
                cnt += 1
                break
        elif arr[start] + arr[end] > goal:
            end -= 1
        elif arr[start] + arr[end] < goal:
            start += 1

print(cnt)