👍🏻 좋다
문제
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)