백준 1253 c++ 좋은 수 구하기

접근 방법

1. set에 N개의 수를 넣어서 중복되지 않도록 하였고
2. 이중 for문을 돌면서 arr[i]+arr[j] 의 값이 1번의 set에 들어있는지 확인하고 sum을 증가시키는 걸로 생각했다.
   for(int i=0;i<N-1;i++){
   for(int j=1;j<N;j++){
   }
   }

그런데 문제를 너무 쉽게 생각했다. 투 포인터로 풀어야 했다. 질문게시판에서 문제에 대한 힌트를 얻었는데 a와 b의 합이 c와 같아야 하며, 자기자신과 같아서는 안된다는 내용이다. 그래서 set<pair<int, int>> 의 형태로 인덱스값과 자신의 값으로 문제를 풀어야할까? 아니면 map<pair<int, int>> 의 형태로 인덱스값과 자신의 값으로 문제를 풀어야할까? 라는 생각이 들었다. 결론적으로는 둘다 틀렸다.

문제 분석

• N의 갯수가 2,000 이므로 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 최소 O(nlogn)이 되도록 해야한다. 따라서 정렬(nlogn)과 투포인터(n^2)을 사용하면 된다.
  ?? 왜??

수열을 정렬하는데 걸리는 시간 복잡도는 𝑂(𝑁log𝑁), 투포인터 알고리즘은 각 숫자 k에 대해 O(N)에 수행할 수 있고 총 N번 반복하므로 O(N^2)이다. O(NlogN)과 O(N^2)을 합해도 O(N^2)이 지배적이므로 전체 시간복잡도는 O(N^2)이다.

• 딱 "두 수"에서 "투 포인터" 유추할 수 있다. 투포인터가 두 개를 표시하는 것이기 때문이다.
• 단 정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함하면 안된다.
• 정렬을 해야한다.

// test.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    int *arr = new int[N];
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    sort(arr, arr+N);
    int count = 0;
    for (int i = 0; i < N; i++) {
        int start = 0;
        int end = N-1;
        int n = arr[i];
        while (start < end && end>=0) {
            int sum = arr[start] + arr[end];
            if (sum < n) {
                start++;
            }
            else if (sum > n) {
                end--;
            }
            else {
                if (start != i && end != i) {
                    count++;
                    break;
                }
            }
        }
    }

    cout << count;
}

• a라는 수와 b라는 수의 합이 c라고 할때, a != c이고 b!=c 이어야한다는 문제의 조건이 있다. 따라서 a+b == c 이면서 a!=c && b!=c 를 만족해야한다.