[BOJ][🟡4][백준#01253] 좋다

문제 출처

BAEKJOON Online Judge #1253

문제

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

My Sol

import sys
input = sys.stdin.readline

def main():
    def is_good(k):
        target = nums[k]
        s, e = 0, N-1
        while True:
            if s==k: s+=1
            if e==k: e-=1
            if s >= e: break
            cur_sum = nums[s]+nums[e]
            if cur_sum == target: return True
            if cur_sum > target: e-=1
            else: s+=1
        return False

    N = int(input())
    nums = sorted(list(map(int, input().split())))
    ret = 0
    for k in range(N):
        ret += is_good(k)
    return ret

print(main())

어렵게 생각했는데, 투포인터를 이용해 쉽게 해결할 수 있는 문제였다.

1. 우선 입력을 받아주는데, 수는 투포인터를 위해 정렬해서 처리한다.
2. 정렬된 모든 수를 대상으로 확인한다. is_good 함수를 이용해 해당하는 인덱스의 수를 만들 수 있는지 확인한다.
3. is_good 함수는 k번째 인덱스의 값을 target으로 둔다. 투포인터의 양쪽 인덱스를 각각 s, e로 설정하고 0과 N-1로 초기화한다. 수의 범위는 음수, 0, 양수이므로 가장 큰 값과 가장 작은 값이더라도 적당한 수를 만들어낼 수 있기 때문이다.
4. 두 인덱스의 값들을 더한 값을 보며 범위를 좁혀가는데, 이때 인덱스가 목표 인덱스인 k라면 s의 경우 1을 더하고, e의 경우 1을 빼 처리한다.
5. 만약 더한 값이 목표치인 target과 같다면 좋은 수라는 의미로 True를 반환하고, 크다면 e를 1 줄이고 작다면 s를 1 늘려 다시 확인한다.
6. 이를 s가 e와 같거나 커지는 순간까지 반복하는데, 이 사이에 해당하는 수를 찾을 수 없다면 False를 반환한다.
7. True면 1, False면 0을 ret에 더하는데, 모든 수에 대해 실시한 누적값 ret을 main 함수에서 반환하여 출력한다.

결과

맞았습니다!!