BOJ 1253 : 좋다

풀이 요약

투 포인터를 활용한 문제

풀이 상세

1. 이 문제는 음수가 존재한다는 것을 파악하는 것이 중요하다. [1,2,3] 의 경우, 3의 인덱스보다 작은 인덱스만 살펴보면 되기에 0~idx-1 로 설정하면 되지만, [-3,-2,-1] 의 경우에는 idx+1~N-1 로 설정해야 한다. 단 음수, 양수 모두 혼합되어 나올 것이므로, 탐색 시 그냥 모든 범위로 정하는 것이 좋다.

2. l 을 시작점, r 을 끝점으로 하여,

   • 현재 두수의 덧셈이 비교하는 수보다 작다면, l++
   • 현재 두수의 덧셈이 비교하는 수보다 크다면, r++
   • 현재 두수의 덧셈이 비교하는 수와 일치하는데, 현재 비교하는 수의 인덱스와 l 혹은 r 이 같은 경우가 아니라면, 그 수는 $GOOD$ 이 된다.

배운점

• 시간 복잡도가 계산하는 것이 정확히 어떻게 되는지 아직도 잘 분간하지 못한다. 투 포인터 쓰면 시간초과 나오지 않을까 했는데, 시간이 초과되지 않았던 문제.

• 배열의 경우, 30만 이상이라면 에러를 나타낸다. 그래서 방문처리를 위해 맵을 사용했는데, C++의 맵을 배열을 탐색하듯 인덱스로 찾으면 ex)m[i] int 의 경우, idx:0 의 맵이 생성된다!

• 방문처리로 map 을 쓰긴 하였으나, 시간 출력은 동일했다. 태케에 중복되는 덧셈이 많지 않았나 보다.

• 젯브레인의 C 언어 IDE 인 cLion 을 써봤다. 알고용으로 정말 좋다. 디버깅도 빨리 움직이고 출력도 입력과 겹쳐서 나오지 않는게 좋다. 무엇보다 intelliJ 랑 단축어도 거의 동일해서 좋다.

코드

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int N, ans;
vector<int> v;
map<int, int> m;

void input() {
    cin >> N;
    int num;
    for (int i = 0; i < N; i++) {
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end());
}

void solve() {
    for (int i = 0; i < N; i++) {
        int curr_num = v[i];
        int l = 0;
        int r = N - 1;
        if (m[curr_num]) {
            ans++;
            continue;
        }
        while (l < r) {
            int sum = v[l] + v[r];
            if (sum == curr_num) {
                if (i == l) l++;
                else if (i == r) r--;
                else {
                    m.insert({sum, 1});
                    ans++;
                    break;
                }
                continue;
            }
            if (sum < curr_num) l++;
            else r--;
        }
    }
}

void output() { cout << ans; }

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    solve();
    output();
    return 0;
}