백준 27931번 - Parity Constraint Closest Pair

#include <iostream>
#include<algorithm>
#include<typeinfo>
#include <vector>

using namespace std;

bool comp(pair<int, string> a, pair<int, string> b) {
    return a.first < b.first;
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;

    vector<int> odd_mem;
    vector<int> even_mem;

    int odd_result = 200000001;
    int even_result = 200000001;

    for (int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;

        //홀수
        if ((tmp & 1) == 1)
            odd_mem.push_back(tmp);
        //짝수
        else
            even_mem.push_back(tmp);

    }   
    
    if (odd_mem.size() != 0)
    {
        sort(odd_mem.begin(), odd_mem.end());
    }
    if (even_mem.size() != 0)
    {
        sort(even_mem.begin(), even_mem.end());
    }

    //do solution   
    //홀 - 홀 = 짝 
    //홀 - 짝 = 홀
    //짝 - 짝 = 짝
   
    //작은 짝수 찾기
    for (int i = 1; i < odd_mem.size(); i++) {
        even_result = min(odd_mem[i] - odd_mem[i-1], even_result);
    }
    for (int i = 1; i < even_mem.size(); i++) {
        even_result = min(even_mem[i] - even_mem[i-1], even_result);
    }

    //작은 홀수 찾기
    int tmp = 0;
    if(even_mem.size() != 0 && odd_mem.size() != 0)
        for (int i = 0; i < odd_mem.size(); i++) {
            for (int j = tmp; j < even_mem.size(); j++) {
                if (odd_mem[i] - even_mem[j] < 0) {
                    odd_result = min(odd_result, even_mem[j] - odd_mem[i]);
                    tmp = j;
                    break;
                }
                odd_result = min(odd_result, odd_mem[i] - even_mem[j]);
            }
        }
   
    if (even_result == 2000000001)
        even_result = -1;
    if (odd_result == 2000000001)
        odd_result = -1;
    cout << even_result << " " << odd_result;
    return 0;
}

직관적으로 풀면 하나의 N^2방식으로 풀수 있지만 100점을 얻기 위해서는 홀 짝특이성을 이용하여 계산 횟수를 줄여준다

 

1. vector.size()가 unsigned라는 것을 모르고 -1을 했다가 고생좀 했다

2. 10^9승까지 범위 제한으로 최대 20억까지 값이 나타날수 있어 int로 해결이 가능하다

 

다른 분들은 메모리 사용량이 나의 절반이던데 어떻게 했는지 궁금하다 ㅠㅠ