👍🏻 좋다

27 Jul 2022 in Algorithm on Two pointer

백준 Gold4

좋다

문제

---

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

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

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

입력

---

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

출력

---

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

예제 입력 1

10
1 2 3 4 5 6 7 8 9 10

예제 출력 1

8

힌트

---

3,4,5,6,7,8,9,10은 좋다.

📖 Two Pointer

투포인터는 [특정한 합을 가지는 부분 연속 수열]을 구할때 쓴다.

글로 표현하기에는 이해가 안 갈 수 있으니 예시를 통하여 설명을 해보도록 하겠다.

배열이 1,2,3,2,5로 주어지고 배열의 연속합이 “5”가 되는 부분 수열이 몇 개인지 찾는다고 가정해보자.

시작 포인터와 끝 포인터를 초기화 해주고 끝 포인터를 오른쪽으로 옮기며 누적합을 구한다.

그러다가 누적합이 찾고자 하는 수보다 커지는 순간이 온다면 시작 포인터를 오른쪽으로 옮긴다.

왜냐하면 포인터를 조정하여 누적합을 바꿀 수 있기 때문이다.

• 누적합 ⬇️ 👉🏻 시작 포인터 오른쪽
• 누적합 ⬆️ 👉🏻 끝 포인터 오른쪽

만약, 누적합이 우리가 찾고자 하는 수와 같다면 개수를 증가시킨다.

이를 끝까지 반복하면 우리는 최종적으로 부분 수열의 개수를 찾을 수 있다.

왜 투포인터를 사용하는가?

이 문제에서는 [어떤 수]가 [다른 수 두 개의 합]으로 나타낼 수 있는지를 묻고 있다.

[어떤 수] 👉🏻 특정한 합 [다른 수 두 개의 합] 👉🏻 부분 연속 수열

위와 같이 해당하기 때문에 투포인터를 떠올릴 수 있어야 한다.

물론 나는 알고리즘 분류를 보고 깨달았다. 하하하 😅

📐 설계

TRY 1

첫 번째 설계의 실패 이유는 포인터 위치를 동일한 경우도 포함시켰기 때문이다.

투포인터에 대하여 풀었던 문제들이 조금 있었지만 그 동안 헛공부를 한 것인지 기억이 제대로 안 났다.

그래서 추가적인 공부를 한 내용이 위의 내용인데 예시에 대한 기억이 그대로 남아있어서인지 무의식적으로 문제 조건을 간과한 채 포인터를 겹쳐놓았다.

이 문제에서 묻는 것은 2개의 수를 합하는 것인데 포인터가 겹쳐지게 되면 1개의 수를 의미하게 되므로 반례가 생긴다.

TRY 2

[시작 포인터 < 끝 포인터] 조건을 만족시키기 위하여 끝 포인터를 배열 끝부터 설정해놓고 이동시켰다.

👨🏻‍💻 CODE

TRY 1

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int,input().split()))

arr.sort()
good_count = 0

for i in range(N):
    check = arr[:i] + arr[i+1:]
    summary = 0
    m = arr[i]
    end = 0

    for start in range(N-1):
        if check[start] > m:
            break
        while summary < m and end < N-1:
            if start == end:
                summary = check[start]
            else:
                summary = check[start]+check[end]
            end +=1
        if summary == m:
            good_count += 1
            break

print(good_count)

TRY 2

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int,input().split()))

arr.sort()
good_count = 0

for i in range(N):
    check = arr[:i] + arr[i+1:]
    start,end = 0,N-2
    sum = 0
    target = arr[i]

    while start < end:
        sum = check[start]+check[end]

        if sum == target:
            good_count += 1
            break
        
        if sum > target:
            end -= 1
        
        if sum < target:
            start += 1

print(good_count)