[C++] BOJ 18870번: 좌표 압축

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다. 문제의 난이도는 실버 2이다.

문제 링크

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

문제 분석

해당 문제는 배열을 정렬하는 과정이 필요한 문제이다.

 

배열을 정렬한 이후 문제를 2중 for문으로 풀 수 있다고 생각하였으나, 그렇게 풀 경우 빅오 표기법 상으로 O(n 제곱)이 되어 큰 input에 대해서는 2초 내로 문제를 해결할 수 없게 된다. 즉, 시간 초과가 나게 된다.

 

따라서 배열을 정렬하는 것 외에도 시간 제한 2초 내로 문제를 풀 수 있도록 하는 방법이 필요했다.

 

시간 제한을 해결할 다른 방법도 있을지 모르겠으나 필자는 map 자료구조를 활용하여 이러한 문제를 해결하였다.

문제 풀이

먼저 입력으로 받은 배열 x에 대하여 정렬된 배열인 sorted_x를 만들어 주었다. sorted_x는 x의 값을 복사하고, 값을 정렬한 배열이다.

int x[1000002]; // 배열의 크기는 문제의 제약 조건을 보고 1000000보다 조금 큰 수로 지정해주었다.
int sorted_x[1000002];

for (int i = 0; i < N; i++)
{
    cin >> x[i];
    sorted_x[i] = x[i]; //sorted_x 배열로 x 배열의 값을 복사
}

sort(sorted_x, sorted_x + N); // sorted_x 배열의 값을 정렬

값을 정렬하는 이유는 좌표 압축을 계산할 때에 크기 순서대로 정렬한 후 계산해야 하기 때문이다.

 

그리고 좌표 압축한 값을 계산하기 위해 map 자료구조를 활용하여 값을 입력받을 때마다 각 배열 x의 값을 key로, value를 0으로 갖도록 만들어주었다. map 자료구조를 활용하여 배열 x를 좌표 압축한 값을 계산할 것이다.

map<int, int> m;

for (int i = 0; i < N; i++)
{
    cin >> x[i];
    sorted_x[i] = x[i]; //sorted_x 배열로 x 배열의 값을 복사
    m[x[i]] = 0; // key값인 x[i]에 대하여 value를 0으로 지정
}

 

여기서 map 자료구조를 활용하는 이유는 마지막에 결과를 출력할 때에 x[i]에 대응되는 좌표 압축한 결과를 출력하고 싶기 때문이다. 아래와 같은 코드로 말이다.

for (int i = 0; i < N; i++)
    cout << m[x[i]] << ' ';

이제 좌표 압축한 값을 계산해 보자. 좌표 압축을 계산하는 방법을 코드로 나타내면 다음과 같다.

for (int i = 1; i < N; i++)
{
    if (sorted_x[i - 1] < sorted_x[i])
        m[sorted_x[i]] = m[sorted_x[i - 1]] + 1;
}

 

여기서 i의 초기값이 0이 아닌 1임에 유의해야 한다. i가 0일 때 m[sorted_x[i - 1]]에 접근한다면 문제가 발생하므로 i가 1일 때부터 연산을 시작한다.

참고로 i가 0에 대해서 처리하지 않아도 되는 이유는 m[sorted_x[0]]은 초기값과 같은 0이 되어야 하기 때문이다.

전체 코드

위의 작업을 종합해 작성한 전체 코드는 다음과 같다.

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int N;
int x[1000002];
int sorted_x[1000002];

map<int, int> m;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> x[i];
        sorted_x[i] = x[i];
        m[x[i]] = 0;
    }

    sort(sorted_x, sorted_x + N);

    for (int i = 1; i < N; i++)
    {
        if (sorted_x[i - 1] < sorted_x[i])
            m[sorted_x[i]] = m[sorted_x[i - 1]] + 1;
    }

    for (int i = 0; i < N; i++)
    {
        cout << m[x[i]] << ' ';
    }
    cout << '\n';

    return 0;
}

 

결과