백준 알고리즘(BOJ)_1253번['좋은 수' 구하기]

'좋은 수' 구하기[1253번]

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

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

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

 

입력

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

 

출력

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

예제

---

문제 분석

N의 개수가 최대 2,000이라 가정해도 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 N2보다 작아야 함

좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 최소 O(nlogn)이어야 함

정렬된 리스트를 투 포인터 알고리즘을 사용하여 두 정수의 합이 해당 K값과 같은지 비교하면서 좋은 수 개수 구하기

(단, 정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함하면 안됨 → K의 인덱스 값과 두 수의 인덱스 값이 같으면 안됨

[투 포인터 이동 원칙]
• A[i]+A[j] > K: j--;
• A[i]+A[j] < K: i++;
• A[i]+A[j] == K: count++; 프로세스 종료

---

슈도코드 작성

1. 수의 개수 N입력받기
2. 리스트 A 입력받기
3. 리스트 A 정렬
4. for k in range(N): k가 N이 될때까지 탐색
	i=0		포인터 값 초기화
    j=N-1
    K=A[k] 판별 대상인 수 K값 지정
    while i<j:  i와 j가 만나기 전까지 반복
    	투포인터 이동 원칙 이용
        ⭐️ k가 i와 같거나, k가 j가 같은 경우는 제외해주어야 함(자기 자신은 좋은 수 만들기에 포함하면 안됨)
5. 좋은 수의 개수 출력

---

코드 구현

import sys
input=sys.stdin.readline
N=int(input()) #수의 개수
A=list(map(int, input().split()))  #N개의 수 값 A리스트
A.sort()  #리스트 정렬
count=0
for k in range(N):  #K가 N개가 될 때까지 반복
    i=0  #i와 j를 배열 A 양쪽 끝에 위치
    j=N-1
    K=A[k] 
    while(i<j):  #i와 j가 만나기 전까지 반복
        #투 포인터 이동 원칙
        if (A[i]+A[j])>K: 
            j-=1
        elif (A[i]+A[j])<K:
            i+=1
        else:
            if k==i: #자기 자신이 좋은 수가 되는 경우 제외
                i+=1 
            elif k==j: #자기 자신이 좋은 수가 되는 경우 제외
                j-=1
            else:
                count+=1  #count값 증가시키고
                break #프로세스 종료
print(count)