[C언어] Set (정렬 기반 중복 제거 알고리즘)

1이라 쓰고 8이라 읽는다

문제

Set

사용자로부터 한 줄로 전체 개수를 알 수 없는 정수들을 입력받아서, 순서대로 정렬하여 처음부터 끝까지 출력할 수 있도록, 정수를 저장하는 집합을 구현하세요.

• 집합이기 때문에 입력받은 숫자 중 중복된 것이 있을 경우 하나만 출력합니다.
• 입력은 공백으로 구분되어서 들어옵니다.
• 출력 시에 원소들은 쉼표로 구분하여 출력합니다.

입출력 예시

(입력 #1)

1 6 2 6 4 2 1 5 3 6 231 6 3 21 3 32 52 5 12 4243 5 23 412 1 2 3 2

(출력 #1)

1, 2, 3, 4, 5, 6, 12, 21, 23, 32, 52, 231, 412, 4243

 

어떻게 풀까?

2가지 방법을 생각해보았다.

하나는 구현이 단순한 방법으로 배열을 활용해 체크하는 것이다.

long long으로 양수와 음수를 저장할 Pos, Neg라는 배열을 1억 자리정도 배정하고 0으로 초기화 한다.

그 다음 특정 수를 확인하면 그 수에 해당하는 인덱스의 값을 1로 바꿔준다. 그러면 같은 수가 몇개가 오더라도 나왔는지 아닌지 확인할 수 있다.

이런식으로 한 다음 음수부터 양수 범위까지 선형적으로 훑고 값이 1인 곳의 인덱스를 반환해 출력해 주는 방법이다.

 

다른 방법은 입력을 모두 받고, 정렬한 다음, 새로운 배열에 중복이 되는 부분을 체크한 다음, 중복되지 않은 수들을 모두 출력하는 것이다.

 

코드를 살펴보자

#include <stdio.h>
#include <stdlib.h>
#define ll long long
ll neg[10101010]={0};
ll pos[10101010]={0};
ll num;
ll min = 0;
ll max = 0;
char buf;

int main(int argc, char *argv[]) {

    while(1)
    {

        scanf("%lld",&num);
        buf = getchar();
        if(buf == '\n' || buf == EOF)
            scanf("%lld",&buff[cnt++]);
        if(num < min)
            min = num;
        else if(num > max)
            max = num;
        if(num < 0)
        {
            num *= -1;
            neg[num] = 1;
        }
        else
        {
            pos[num] = 1;
        }
    }
    for(ll i=-min; i>0; i--)
        if(neg[i])
            printf("%lld, ",i*-1);
    for(ll i=0; i<max; i++)
        if(pos[i])
            printf("%lld, ",i);
    if(pos[max])
        printf("%lld",max);
    printf("\n");
    return 0;
}

첫 번째 알고리즘은 이런 식으로 구현했었다.

성공적으로 작동하였지만 문제가 하나 있는데, 바로 100200300같은 너무 큰 수는 다루지 못한다는 점이다.

실제로 배열의 범위를 넘어서는 인덱스 때문에 첫번째 알고리즘은 실패이다.

 

#include <stdio.h>
#include <stdlib.h>
#define ll long long
ll buff[101010];
ll res[101010];
char bl;
ll cnt=0;
ll now, bf;
int static compare(const void*first, const void*second)
{
	if(*(ll*)first > *(ll*)second)
		return 1;
	else if(*(ll*)first < *(ll*)second)
		return -1;
	else return 0;
}
int main(int argc, char *argv[]) {
	while(1)
	{
		scanf("%lld",&buff[cnt++]);
		bl = getchar();
		if(bl == '\n' || bl == EOF)
			break;
	}
	qsort(buff,cnt,sizeof(ll),compare);
	res[0] = buff[0];
	ll N=1;
	for(int i=1; i<=cnt-1; i++)
	{
		if(res[N-1] == buff[i])
			continue;
		else
			res[N++] = buff[i];
	}
	for(int i=0; i<N-1; i++)
		printf("%lld, ",res[i]);
	printf("%lld\n",res[N-1]);
	return 0;
}

 두번째 알고리즘 코드는 이렇다.

보면 알 수 있듯, stdlib.h에 있는 qsort를 이용해 입력받은 배열을 정렬해주었다.

 

	res[0] = buff[0];
	ll N=1;
	for(int i=1; i<=cnt-1; i++)
	{
		if(res[N-1] == buff[i])
			continue;
		else
			res[N++] = buff[i];
	}

이 부분을 보면 알 수 있듯

res의 N-1번 인덱스의 값과 buff에 들어갈 현재 인덱스의 값이 같다면 다음 요소를 비교, 같다면 res배열의 N번째에 넣어주는 짓을 반복하고 있다.

이런 식으로 하면 입력의 시간 복잡도 O(n), 정렬의 시간복잡도 O(nlogn), 중복제거의 시간 복잡도 O(n), 출력의 시간복잡도 O(n)으로 전체 O(nlogn)의 시간복잡도를 갖는다.