[코드포스 Practice22] D. Uniqueness

 

문제 이해는 했는데 어떻게 풀지 몰라서 못 푼 문제였다. 나름 구간이 있어서 투포인터랑 부분합이 떠올랐고 또 구간의 최소 길이를 구하는 문제니깐 파라매트릭 서치도 생각 났는데 전부 활용하기 어려웠다. 투포인터는 l, r 한 번씩 훑는다고 최소 길이를 찾기 어려웠고 부분합은 여기 쓰는 건 아닌 듯하다. 파라매트릭 서치는 답이 있는 구간이 정확히 두 개의 구간으로 나눠지지 않아서 쓰기 어렵다. 

 

이 문제의 힌트는 n이 작다! n이 2000 이하의 값이라 n^2까지 계산이 가능하다. 또 이걸 구간의 최소를 구하는 건 구간 외의 길이가 최대가 되면 된다. 그래서 구간 밖의 오른쪽과 왼쪽이 중복되지 않는 최대의 길이를 구해보자. 

 

 

갑자기 손코딩이 해보고 싶었음

 

메모리 얼마나 쓰는지도 배웠다. 배열 크기에 자료형 크기 곱하고 백만 나눠주면 몇 MB 쓰는지 알 수 있다. 256을 넘기지 말도록 하자.

 

 

엄청난 디버깅의 현장

 

이 문제 한 번 틀렸었다.. 아무리 찾아도 왜 틀린지 몰라서 해맸는데 알고보니 map에 대한 이해가 부족해서 생긴 문제였다 (!) 처음에 len의 길이를 구할 때 int len = calcL.size(); map의 크기를 길이로 뒀었다. 그런데! map에 값을 따로 넣지 않아도! if (calcR[v[i]] > 1 || calcL[v[i]] > 1) 이렇게 조건을 확인 하면 map에 값이 들어간다 ㅜㅜㅜㅜ 이것 때문에 계속 찾았는데 너무 허무하다... int len = i;로 두니 통과했다. 증맬... 

 

---

좌표압축으로 구현하기

 

위 코드로 구현하면 시간 복잡도는 O(N^2logN)이다. 왼쪽에서 확인하는 부분이 N이고 오른쪽으로 확인하는 부분이 N이고 map을 사용해 좌표를 찾는 부분이 logN이다. 여기서 좌표압축을 사용하면 map의 시간복잡도를 줄일 수 있다. 

 

int main()
{
    int n;
    scanf("%d", &n);
    
    vector<int> arr(n);
    
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
        
    vector<int> sorted = arr;
    sort(all(sorted));
    sorted.erase(unique(all(sorted)), sorted.end());
    
    for (int i = 0; i < n; i++)
        arr[i] = lower_bound(all(sorted), arr[i]) - sorted.begin();
    
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    
    return 0;
}

 

 

이걸 클래스로 만들면 아래와 같다.

 

좌표압축을 사용해서 코드를 구현했다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAX 1e9
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

class Mapping
{
  public:
    void init(const vector<i64>& raw, int base = 0)
    {
        start = base;
        arr = raw;
        sort(arr.begin(), arr.end());
        arr.erase(unique(arr.begin(), arr.end()), arr.end());
    }

    int get_idx(int k)
    {
        return start + lower_bound(all(arr), k) - arr.begin();
    }

    int get_value(int idx)
    {
        return arr[idx - start];
    }

    int size()
    {
        return arr.size();
    }

  private:
    int start;
    vector<i64> arr;
};

int main() {
    int n;
    scanf("%d", &n);
    
    vector<i64> v(n);
    for (int i = 0; i < n; i++)
        scanf("%lld", &v[i]);
    
    Mapping m;
    m.init(v);

    for (int i = 0; i < n; i++)
        v[i] = m.get_idx(v[i]);

    vector<int> calcL(n, 0);
    int minL = n;
    
    for (int i = 0; i < n; i++)
    {
        vector<int> calcR(n, 0);
        int len = i;
        
        for (int j = n-1; j >= i; j--)
        {
            calcR[v[j]]++;
            
            if (calcR[v[j]] > 1 || calcL[v[j]] >= 1)
                break;

            len++;
        }
        
        if (n-len < minL)
            minL = n-len;
 
        calcL[v[i]]++;
        
        if (calcL[v[i]] > 1)
            break;
    }
    
    printf("%d\n", minL);
    
    return 0;
}