📘 문제

문제링크 : https://www.acmicpc.net/problem/3273 (단계별로 풀어보기 : 투 포인터)

📝 문제 풀이

처음 문제를 풀때 시간복잡도를 생각을 깊게 생각하지 않았다. 알고리즘스케치를 보면 1,2번은 결국 똑같은 시간복잡도 O(n^2) 이다. 그러므로 n이 최대 100000, 즉 최대 1억반복에 1초라 했을때 100초나 걸릴 수 있다. 그렇기에 2번 방식으로 작성하였다고 시간초과가 났다. 투포인터에 대해서 찾아보다가 정렬을 보자마자 아차 싶었다. 내장 sort 정렬 시 시간 복잡도는 O(nlogn)이다. 그리고 투포인터를 사용하여 탐색을 하면 O(n) 이 나오므로 전체 시간 복잡도는 O(nlogn)이다. 해당 문제의 오답률이 높은 이유는 시간초과 문제일 것 같다. 그런데 만약 문제에서 배열에 중복된 값이 입력가능 하였다면 문제는 다시 더 어려워진다. 해당 풀이가 가능한 것은 중복된 값이 배열에 존재하지 않는다는 조건 때문이다. 이제 이 방식으로 코드를 작성하는 것은 어렵지 않다. 그리고 코딩을 하면서 vector와 배열을 둘다 사용해봤는데 메모리 관점에서 배열이 더 좋았다. 전역 변수를 사용하지 않으려고 포인터를 사용하였지만, 포인터 사용이 미숙하다면 전역변수로 사용해서 작성해라.

✏️ 알고리즘 스케치

💻 소스코드

#include <iostream>
#include <algorithm>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int* input(int* n, int* x);
void solution(int* a, int n, int x);

int main(){
    fastio;
    int* a;
    int n, x;
    a = input(&n, &x);
    solution(a, n, x);
    return 0;
}

int* input(int* n, int* x)
{
    cin >> *n;
    int* a;
    a = new int[*n];
    for(int i=0; i<*n; i++){
        cin >> a[i];
    }
    cin >> *x;
    return a;
}

void solution(int* a, int n, int x)
{
    if(n == 1){
        cout << 0;
        return;
    }
    sort(a,a+n); // 정렬
    int sol = 0;
    int ptr1=0, ptr2=n-1, sum;
    while(ptr1<ptr2){
        sum = a[ptr1] + a[ptr2];
        if(sum<x){
            ptr1++;
        }
        else if(sum>x){
            ptr2--;
        }
        else{
            sol++;
            ptr1++, ptr2--;
        }
    }
    cout << sol;
}