[백준/파이썬] 1253번 좋다

※ 문제

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

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

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

※ 입력

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

※ 출력

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

※ 힌트

3,4,5,6,7,8,9,10은 좋다.

※ 해결방법

일단, 단순하게 좋은 수 하나를 찾는 알고리즘을 조건을 사용하여서 문제를 풀려고하면 주어진 시간 내에 코드를 실행시킬 수 없다. 왜냐하면 조건을 사용하여서 문제를 해결하는 접근 방식은 하나의 수를 찾는데 시간 복잡도 O(n^2)의 시간을 필요로 하므로 총 O(n^3)의 시간 복잡도를 가지게 됨을 알 수 있다.

 

그러므로 시간 복잡도를 줄이는 방법을 선택하여서 문제를 해결해야 하므로 조금 더 복잡한 문제라고 할 수 있다.

 

우리는 이 문제를 해결하기 위해서 정렬, 투 포인터 알고리즘을 사용해야 한다.

• 배열 정렬 : 투 포인터를 사용하기 전에 배열을 정렬한다.
• 포인터 초기화: 각 요소를 목표 값으로 설정하고, 배열의 시작(i)과 끝(j)에 포인터를 둔다.
• 포인터 이동: 

A[i] + A[j] > M : j--    # 번호의 합이 M보다 크므로 큰 번호 index를 내린다. 

A[i] + A[j] < M : i++  # 번호의 합이 M보다 작으므로 작은 번호 index를 올린다.

A[i] + A[j] == M : i++, j-- / count ++  # 양쪽 포인터를 모두 이동시키고 count를 증가시킨다.

• 반복: 각 요소를 목표 값으로 설정하여 전체 배열을 탐색한다.

이 문제를 해결하기 위해서는 값은 서로 다른 두 수의 합이라는 조건을 충족시켜야한다.

---

※ 파이썬 코드 정리

 

import sys
input = sys.stdin.readline

a = int(input())
cnt = 0  # 좋은 수의 개수를 세기 위해서 cnt 변수 추가
lst = list(map(int, input().split()))
lst.sort()

for k in range(a):
    cor = lst[k]  # 현재 목표값
    i = 0
    j = a - 1
    while i < j:
        if lst[i] + lst[j] == cor:
            if i != k and j != k:
                cnt += 1
                break
            elif i == k:
                i += 1
            elif j == k:
                j -= 1
        elif lst[i] + lst[j] < cor:
            i += 1
        else:
            j -= 1

print(cnt)