투 포인터 - (3)

좋은 수 구하기 (백준 1253번, 시간 제한: 2초)

문제
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
수의 위치가 다르면 값이 같아도 다른 수이다.

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

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

입력 예시
10
1 2 3 4 5 6 7 8 9 10

출력 예시
8

코드 예시

import sys
input=sys.stdin.readline
n=int(input())
arr=list(map(int,input().split()))
arr.sort()
count=0
for s in range(n):
    i=arr[s]
    start=0
    end=n-1
    while start<end:
        sum=arr[start]+arr[end]
        if sum==i:
            if end==s:
                end-=1
            elif start==s:
                start+=1
            else :
                count+=1
                break
        elif sum>i:
            end-=1
        else:
            start+=1
print(count)

우선 n=2000 이기 때문에 시간복잡도는 O(n^3)을 넘어서는 안된다.

sorting을 먼저 한다.
1 2 3 4 5 6 7 8 9 10
이렇게 있으면
반복문을 2번 돈다.

첫 outer 반복문에서는 find 숫자를 찾는다.
예를 들어 arr[find]=3이라면
start, end를 양 끝으로 두고 arr[start]+arr[end]==find 일때 start!=find 이고 end!=find 일 때만 count를 증가시킨다. 그리고 break (다른 두 수를 더했을 때 find 가 되야 하기 때문이다.)
같은 수가 나왔을 경우에도 index 가 다르면 다른 수로 본다.
이외의 경우에는 투 포인트 문제 처럼 end--, start++ 하면 된다.

핵심: 어차피 좋은 수만 구하면 되기 때문에 같은 숫자들이 반복되도 find는 각 1번만 찾으면 된다. break를 거는 이유!!

c++

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    int A[n];
    for(int i=0;i<n;i++){
        scanf("%d",&A[i]);
    }
    sort(A,A+n);
    int count=0;
    for(int k=0;k<n;k++){
        int find=A[k];
          int i=0;
        int j=n-1;
        while(i<j) {
            if(find==A[i]+A[j]){
                if(i==k)
                i++;
                else if (j==k)
                j--;
                else {count++;break;}
            }
            else if(find>A[i]+A[j])
            i++;
            else j--;
        }
    }
    printf("%d",count);
    return 0;
}

확실히 c++ 이 메모리나 시간적인 측면에서 훨씬 효율적임을 알 수 있다.