백준 1253 좋다 파이썬

🔗 백준 1253 좋다 

 

📌오늘의 학습 키워드

• 투 포인터

✨공부한 내용 본인의 언어로 정리하기

• 투 포인터를 활용하면 N제곱이 걸릴수도 있는 문제를 N만에 풀 수 있다. 

1. 숫자 배열이 들어오면 일단 정렬을 해준다. 
2. 어떤 값에 대해서 그 값을 뺀 배열을 생성해 준다.
3. 해당 배열에서 포인터를 각각 배열의 맨 앞(제일 작은 수), 맨 뒤(제일 큰 수)로 배치한다.
4. 만약 두개의 포인터 값을 합친 것이 타겟 숫자보다 작으면 앞 포인터의 숫자를 높혀준다. - 이렇게 해주면 숫자가 커진다.
5. 만약 작다면 뒤 포인터의 숫자를 줄여준다.
6. 결론적으로 두개의 포인터의 합으로 타겟 숫자를 만들 수 있으면 통과!

직접 그려봤습니다

📚오늘의 회고

• 2중 for문으로 시도했으나 시간 초과
• 투포인터를 적용했으나 틀렸습니다
  • 음수인 경우를 고려하지 않아서 생긴 문제였다.

[🤓문제 해결 코드]

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

nums.sort()
answer = 0

def find_good(idx, new_nums):
    first = 0
    second = len(new_nums) - 1
    while first < second:
        sum_num = new_nums[first] + new_nums[second]
        if sum_num == nums[idx]:
            return 1
        elif sum_num < nums[idx]:
            first += 1
        else:
            second -= 1
    return 0

for i in range(len(nums)):
    new_nums = nums[:i] + nums[i + 1:]
    answer += find_good(i, new_nums)

print(answer)