[백준/Python] 1253번 좋은 수 구하기

1️⃣문제 설명

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

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

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

2️⃣입력

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

3️⃣출력

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

---

👩🏻‍💻작성한 코드

import sys

input = sys.stdin.readline

n = int(input())	# 입력받을 수 개수
num = list(map(int, input().split()))	#입력 받은 n개의 데이터
num.sort()
cnt = 0

for i in range(n):
    good = num[i]
    s = 0
    e = n-1
    while s < e:
        if num[s] + num[e] == good:
            if s != i and e != i:
                cnt += 1
                break
            elif s == i:
                s += 1
            elif e == i:
                e -= 1
        elif num[s]+num[e] < good:
            s += 1
        else:
            e -= 1
            
print(cnt)

💡코드 설명

s와 e 두개의 포인터를 설정해주었다.

 

정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함하면 안되므로 num[s] + num[e] == good일 때,  if문을 사용해서 s와 e가 i가 아닌지 확인해줘야한다.

 

둘 다 i가 아니고 두 인덱스가 가르키는 데이터의 합이 좋은 수가 될 때 cnt += 1을 해주고,

 

s와 e 둘 중 하나가 i와 같을 때는 포인터를 조정해서 자기 자신을 포함시키지 않도록 해줍니다.

 

그리고 num[s] + num[e] < good일 때는, s += 1 해주어 작은 값을 늘려주고

 

num[s] + num[e]  > good일 때는, e -= 1 해주어 큰 값을 줄여주어 good의 값에 가까워지도록 포인터를 조정해준다.