[Algorithm] 백준 18870 좌표 압축 c++

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

 

풀이

1. 값과 인덱스를 pair로 저장한다.
2. 값을 기준으로 정렬한다.
3. 현재 위치보다 왼쪽에 있는 값들의 개수(현재 값보다 작은 수 카운팅)를 해당 인덱스에 넣는다.
4. ans에 값을 넣기 전, 이전 값과 같은 경우 분기해서 처리한다.

 

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector <pair<int, int>> v;

int main(){
    int n;
    cin>>n;
    int ans[n];

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

        //값과 인덱스 pair로 저장
        v.push_back(make_pair(x, i));
    }

    //값을 기준으로 정렬
    sort(v.begin(), v.end());

    int idx = 0;
    for(int i=0; i<n; i++){
        //현재 값이 이전 값과 같은 경우
        if(i != 0 && v[i].first == v[i-1].first)
            idx--;

        ans[v[i].second] = idx++;
    }

    for(int i=0; i<n; i++)
        cout<<ans[i]<<" ";

    return 0;
}

 

🤐 사족

처음에는 문제를 보고 생각나는대로 코드를 작성했더니 시간초과가 떴다. 해당 코드의 수행시간은 O(N^2)였고, N의 최댓값이 1,000,000 (10^6)이므로 제한 시간인 2초를 초과했던 것이다.

 

알고리즘에서 1초는 연산을 1억번(10^8) 수행하는 정도를 나타낸다. 즉 N = 10^4일 때 O(N^2)의 알고리즘을 수행하는데 1초가 걸린다.

 

시간초과 코드

#include <iostream>
using namespace std;

int x[1000001];
bool flag[1000001];
int ans[1000001];

int main(){
    int n;
    cin>>n;

    for(int i=0; i<n; i++)
        cin>>x[i];

    int minVal;
    int minIdx = -1;
    for(int i=0; i<n; i++){
        bool isFin = true;

        if(minIdx != -1) flag[minIdx] = true;
        minVal = 1000000000;
        for(int j=0; j<n; j++){
            if(!flag[j]){
                isFin = false;
                ans[j]++;
                if(minVal > x[j]){
                    minVal = x[j];
                    minIdx = j;
                } else if(minVal == x[j]){
                    flag[j] = true;
                }
            }
        }

        if(isFin) break;
    }

    for(int i=0; i<n; i++)
        cout<<ans[i] - 1<<" ";

    return 0;
}