[백준 1253] 투 포인터 알고리즘 - 파이썬 (Python)

좋다

---

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

---

예제 입력

10
1 2 3 4 5 6 7 8 9 10

예제 출력

8

---

투 포인터 알고리즘

1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태입니다.

완전 탐색으로 문제 풀때 시간초과가 나는 경우가 있는데, 투 포인터 알고리즘은 포인터가 한칸 씩 움직이면서 그 변화만 더하거나 빼주면 되므로 시간 복잡도를 줄일 수 있습니다.

 

이번 문제 처럼 두 자연수들의 합을 구하는 것을 예시로 보여드리겠습니다.

실제 문제에선 연속된 수가 아니라 배열 이므로 'A[start_index]'처럼 접근해야합니다.

이해를 돕기위해서 수 그 자체로 연습해봅시다.

만약 6이 좋은수인지 검사하도록 하겠습니다.

 

K = 7

k가 7이므로 7바로 이전부터 end를 잡고 탐색을 시작합니다.

start_index = 1 , end_index = 5 , SUM = 6 ==> 부족하니까 start++;

1

2

3

4

5

7

7

8

9

10

 

start_index = 2 , end_index = 5 , SUM = 2+5 = 7 ==> 좋은 수!

1

2

3

4

5

7

7

8

9

10

---

K = 6

start_index = 2 , end_index = 5 , SUM = 2+5 = 7 ==> 너무 크니까 end--;

2

3

4

5

6

7

8

9

10

start_index = 2 , end_index = 4 , SUM = 2+4 = 6 ==> 좋은 수!

2

3

4

5

6

7

8

9

10

---

파이썬 코드

# two pointer
import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int , input().split()))
num.sort()
cnt =0
for i in range(n):
    goal = num[i]
    i_index = 0
    j_index = n-1
    while i_index<j_index:
        sum = num[i_index] + num[j_index]
        if sum < goal:
            i_index+=1
        elif sum > goal:
            j_index-=1
        else:
            if i_index!=i and j_index!=i :
                cnt+=1
                break
            if i_index == i:
                i_index+=1
            elif j_index == i:
                j_index-=1
print(cnt)