좋다

좋다

문제

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

문제 해석

• 어떠한 수 a 가 리스트 안에 있다면, a를 제외한 나머지 두 수의 합이 a인 수를 좋은 수라고 한다. 그 수의 합을 구하는 것이다.
• 보통 흔히 생각하는 방법이 2중 루프를 돌면서 각 리스트들과 비교해보는 것인데, 그렇게 되면 비교하는 리스트까지 루프를 돌아야 되서 O(n^3)이 된다. 입력 값 크기는 2000개이므로 O(n^3)이 나오게 되면 시간초과가 뜬다.
• 두번째 방식이 two pointer 방식이다.
• 포인터를 2개를 놓고 각자 움직이면서 비교해주는 것이다.
• 주의해야 할 점은 two pointer 알고리즘은 정렬되어 있는 리스트에서만 이용이 가능하다.
  

풀이

• two pointer 알고리즘을 사용하기 위해 lst를 sort() 해준다.
• 리스트 원소 탐색 루프
  • 자신을 제외한 나머지 두 수의 합이 자신과 맞아야 하기 때문에 자신을 제외한 배열을 temp 라는 배열로 다시 선언
  • left는 index 0부터 시작, end는 temp 리스트의 끝 index에서 시작.
  • left나 right가 서로 역전하는 순간 루프가 꺼지게끔 설계
    • a = left 값 + right 값
    • 만약 a == lst[i]
      • count += 1
      • break
      • break를 하는 이유는 예를 들어 5라는 숫자를 두 수의 합으로 찾아야 한다고 하자
      • 그렇다면 (1,4), (2,3)이 있게 된다.
      • 하지만 5라는 좋은수는 한개이다.
      • 그런데 count는 2개가 올라가기 때문에 1개를 찾는순간 break를 해줘야한다.
    • 만약 a > lst[i]
      • 찾으려는 수보다 커지기 때문에 더해주는 값 두개 중 하나가 작아져야 한다.
      • 작아지는 방법은 end index가 줄어드는 수 밖에 없다
      • 왜냐면 정렬되어 있기 때문이다.
      • end -= 1
    • 만약 a < lst[i]
      • 정렬되어 있기 때문에 합한 숫자를 올리려면 left 값을 올려야 한다.
      • left -= 1

import sys

N = int(sys.stdin.readline())
lst = list(map(int, sys.stdin.readline().split()))
lst.sort()

count = 0

for i in range(len(lst)):
    temp = lst[ : i] + lst[i + 1 : ]
    left = 0
    right = len(temp) - 1
    while left < right:
        a = temp[left] + temp[right]
        if lst[i] == a:
            count += 1
            break
        elif lst[i] > a:
            left += 1
        else:
            right -= 1

print(count)

고찰

• two pointer 알고리즘을 처음 알게 되었다.
• 알고 나면 문제를 쉽게 풀 수 있으나, 이 알고리즘을 생각해내는데 꽤 어렵다.
• 나중에 two pointer 알고리즘을 이용하는 문제를 3개 정도 더 풀어봐야겠다.