[백준/BOJ] 18870번: 좌표 압축 - C++ 문제 풀이

문제 설명

 

문제 링크:  https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

 

풀이

처음에는 다른 방식으로 풀었다가 "시간 초과"를 받고 문제가 무엇인지 한참 생각한 문제입니다.

제출한 코드를 위의 입력 예시 정도의 데이터로 검토하는 것이 아닐까라고 간단히 생각했는데 그렇지 않은 모양입니다.

 

이 문제는 입력된 숫자보다 작은 숫자들의 개수를 구하는 문제이다. 그런데 작은 숫자들이 중복된 경우 하나의 숫자로 카운트한다.

 

예를 들어보면

4

3

3

2

2

2

1

숫자 4에 대한 정답은 3이다. 왜냐하면 숫자 3가 2회 나오지만 1회로 카운트한다. 마찬가지로 숫자 2도 1회로 카운트, 마지막 숫자 1도 1회로 카운트돼서 모두 3이다. 4보다 작으면서 서로 다른 숫자의 개수를 4에 대한 값으로 출력하면 된다.

마찬가지로 숫자 3에 대한 정답은 2이다.

 

이 글에서는 문제를 풀기 위해 위의 배열을 그룹화했다. 같은 숫자가 있으면 1부터  시작되는 같은 그룹 번호를 부여하는 것이다. 그렇게 되면 위의 배열은 아래처럼 변경된다. 서로 다른 숫자가 4개 있으므로 총그룹의 수는 4이다.

1

2

2

3

3

3

4

그리고 원래의 숫자 4에 대한 출력값은 4 - 1 = 3 (총그룹의 수 - 그룹번호)로 계산하기 쉬워진다.

숫자 3에 대한 출력은 2이다.

 

int divideGroup(int* buffer, int N){

    int GC = 1; // group count
    
    int cur = buffer[0];
    buffer[0] = GC;		// group number

    for(int i = 1; i < N; i++){
        
        int num = buffer[i];
        
        if ( num != cur){
            cur = num;
            GC++;
        }

        buffer[i] = GC;    // num -> group number
    }

    return GC;
}

 

위의 방식을 쓰려면 입력된 값들의 배열은 큰 수가 앞에 위치해야 한다는 조건을 만족시켜야 한다. 

이 조건은 입력된 데이터를 내림차순으로 정렬하면 될 것이다. 그렇지만 정렬 후, 그룹을 나누고 나면 다시 입력된 순서대로 배열의 순서를 되돌려야 한다. 입력된 값에 대응하는 결과 값을 입력된 순서대로 출력해야 하기 때문이다.

 

정렬하기 전으로 되돌아갈 배열의 인덱스가 필요하다. 그래서 구조체 Pair 사용한다.

struct Pair 
{ 
    int data;
    int idx;  
};

Pair* buffer;

 

buffer ( Pair 구조체 배열 )의 data에 입력값을 넣었다가 정렬 후 그룹 번호로 변경하고, idx에는 입력 시 배열 인덱스를 넣는다. 그 후 총그룹의 수에서 그룹 번호를 뺀 값을 출력 버퍼 res에 넣는다.

 

정렬 시 구조체 Pair의 순서를 정하기 위해 사용자 함수를 사용했습니다.

// 내림차순
bool compare_by_num( const Pair& a,const Pair& b){
    return a.data > b.data;
}

 

sort 함수 사용법에 대해 더 알고 싶다면 다음 링크를 참고해 주세요.

https://codingembers.co.kr/10

[C++] STL sort 함수 사용법

 

int N = readData();

Pair* buffer = new Pair[N];	// 데이터 개수
int* res = new int[N];

for (int i = 0; i < N; i++){
    buffer[i].data = readData();
    buffer[i].idx = i;	// 입력 배열의 인덱스
}
    
sort(buffer, buffer+N, compare_by_num); // 내림차순으로 정렬

int GC = divideGroup(buffer, N);     // group counting

for(int i = 0; i < N; i++){
    int data = buffer[i].data;   // group number

    int restGC = GC - data;  	// 남은 그룹의 개수
    res[ buffer[i].idx ] = restGC;	// 출력 버퍼에 기록
 }

 

위의 방식으로 문제를 제출하면 "맞았습니다" 나옵니다. 그런데도 시간이 꽤 소요되더군요.

이때는 입출력 cin, cout 객체를 사용했습니다.  

 

그래서 혹시 입력/출력 문제인가 하고 빠른 수행속도를 보이는 다른 사람들의 코드를 보니 역시 문제 입력/출력이 시간을 엄청 잡아먹는 것을 알게 되었습니다. 아마 엄청난 양의 데이터로 테스트를 수행하는 모양입니다.

이 문제를 해결하는 방법으로 데이터를 한 번에 읽어낸 후, 메모리에 올라온 데이터를 필요한 크기로 잘라 쓰는 방식을 사용했습니다. ( 전체 소스 참고 )

char buf[12000010];		// 필요한 버퍼의 크기를 어떻게 알지?
fread(buf, 1, sizeof(buf), stdin);

 

재밌는 것은 위의 buf의 크기를 10,000,000로 바꾸니까  "런타임 에러 (OutofBound)"라고 뜨더군요.

12,000,010이라는 숫자를 어떻게 아는 걸까요?

 

 

소스 코드

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

struct Pair 
{ 
    int data;
    int idx;  
};

int divideGroup(Pair* buffer, int N){

    int GC = 1; // group count
    
    int cur = buffer[0].data;
    buffer[0].data = GC;

    for(int i = 1; i < N; i++){
        
        int num = buffer[i].data;
        
        if ( num != cur){
            cur = num;
            GC++;
        }

        buffer[i].data = GC;    // num -> group count
    }

    return GC;
}

// 내림차순
bool compare_by_num( const Pair& a,const Pair& b){
    return a.data > b.data;
}

char buf[12000010];
static int bi = 0;  // buffer idx

inline int readData()
{
	bool flag = false;
	if (buf[bi] == '-')
	{
		flag = true;
		bi++;
	}
	int r = buf[bi++] - '0';
	while (buf[bi] >= '0')
		r = (r * 10) + buf[bi++] - '0';
	while (buf[bi] < '-')
		bi++;
	return flag ? -r : r;
}

inline void writeData(int x)
{
	char s[10];
	int i = 0;
	do {
		s[i++] = x % 10 + '0';
		x /= 10;
	} while (x);
	for (i--; i >= 0; i--)
		buf[bi++] = s[i];
	buf[bi++] = ' ';
}

int main() {
    
    fread(buf, 1, sizeof(buf), stdin);
    int N = readData();

    Pair* buffer = new Pair[N];
    int* res = new int[N];

    for (int i = 0; i < N; i++){
    	buffer[i].data = readData();
    	buffer[i].idx = i;
    }
    
    sort(buffer, buffer+N, compare_by_num); // 내림차순으로 정렬

    int GC = divideGroup(buffer, N);     // group counting

    for(int i = 0; i < N; i++){
        int data = buffer[i].data;   // group number

        int restGC = GC - data;  // 남은 그룹의 개수
        res[ buffer[i].idx ] = restGC;
    }

    bi = 0; // reset buffer counter
    for (int i = 0; i < N; i++){
    	writeData(res[i]);
    }
    buf[bi] = '\0';
    fwrite(buf, 1, strlen(buf), stdout);

    delete [] buffer;
    delete [] res;
    
    return 0;
}