오늘의 코딩#4

오늘도 42서울 프로그램 위주로 코드를 짰고 백준 문제도 2개 풀었다.
통계학, 소트인사이드를 풀었는고 좌표 정령하기 문제를 3번 정도 시도해보고 안돼서 42서울 코드를 짰다.

통계학 문제의 경우 홀수개의 수를 입력받아 산술평균, 중앙값, 최빈값, 범위 를 출력하는 문제이다.

int main(void)
{
int n, i, t, s1 = 0, s2 = 1;
int median, mode, range, min, max, sum = 0;
float mean;
int temp[8001] = {
0,
};

scanf("%d", &n);
for (i = 0; i < n; i++)
{
    scanf("%d", &t);
    temp[4000 + t]++;
}
for (i = 0; i < 8001; i++)
{
    if (temp[i] != 0)
    {
        if (s1 == 0)
        {
            min = i - 4000;
            mode = min;
        }
        max = i - 4000;
        if (s1 < n / 2 + 1 && s1 + temp[i] >= n / 2 + 1)
            median = i - 4000;
        if (temp[4000 + mode] < temp[i])
        {
            mode = i - 4000;
            s2 = 1;
        }
        else if (4000 + mode != i && temp[4000 + mode] == temp[i] && s2 == 1)
        {
            mode = i - 4000;
            s2 = 0;
        }
        sum += (i - 4000) * temp[i];
        s1 += temp[i];
    }
    if (s1 == n)
        break;
}
mean = (float)sum / n;
if (mean - (int)mean / 1 >= 0.5)
    mean++;
if (mean - (int)mean / 1 <= -0.5)
    mean--;
mean = (int)mean / 1;
range = max - min;
printf("%d\n%d\n%d\n%d\n", (int)mean, median, mode, range);
return (0);

}

이렇게 짰는데 변수도 너무 많고 별로 효율적이지도 않은 듯 싶어 아쉽지만 다른 풀이는 생각나지 않아 그냥 놔뒀다.

소트인사이드의 경우 정수를 입력받아 크기순 정렬 시키는 문제인데 사실 문자열로 입력 받으면 되지만 출제 의도에 맞게 풀려고 했다.

#include <stdio.h>

void make_list(int n, char *lst)
{
lst[n % 10]++;
if (n / 10 > 0)
make_list(n / 10, lst);
}

int main(void)
{
int n;
char lst[10] = {
0,
};

scanf("%d", &n);
make_list(n, lst);
n = 0;
for (int i = 9; i >= 0; i--)
{
    while (lst[i] > 0)
    {
        n = n * 10 + i;
        lst[i]--;
    }
}
printf("%d\n", n);
return (0);

}

이렇게 코드가 완성 됐는데 이전에 풀었던 문제를 응용해 정수를 쪼개는 것만 재귀 처리를 했다.

좌표 정렬하기 문제의 경우 이전에 풀었던 수 정렬하기를 좌표에 적용하는 문제였다.
좌표를 100,000개 까지 입력 받아 충분히 감당 가능하다고 생각해서 처음에는 일반적인 정렬 알고리즘을 짰다.

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
int n, i, t;
int *temp;
int **lst;

scanf("%d", &n);
lst = (int **)malloc(sizeof(int *) * (n + 1));
for (i = 0; i < n; i++)
{
    lst[i] = (int *)malloc(sizeof(int) * 2);
    scanf("%d %d", &lst[i][0], &lst[i][1]);
}
for (t = 1; t < n; t++)
{
    for (i = 0; i < n - t; i++)
    {
        if (lst[i][0] > lst[i + 1][0])
        {
            temp = lst[i];
            lst[i] = lst[i + 1];
            lst[i + 1] = temp;
        }
        else if (lst[i][0] == lst[i + 1][0] && lst[i][1] > lst[i + 1][1])
        {
            temp = lst[i];
            lst[i] = lst[i + 1];
            lst[i + 1] = temp;
        }
    }
}
for (i = 0; i < n; i++)
{
    printf("%d %d\n", lst[i][0], lst[i][1]);
    free(lst[i]);
}
free(lst);
return (0);

}

그런데 시간 초과가 됐다.
그래서 시간 복잡도를 낮추기 위해 연결 리스트를 사용해보았는데 처음에 동적할당을 이용 하니까 메모리가 초과됐다.
그래서 그냥 메모리를 할당해주도록 짰다.

#include <stdio.h>

typedef struct _llst
{
int x, y;
struct _llst *next;
} llst;

void add_list(llst *lst, int x, int y)
{
int i = 0;

if (lst->next == 0)
{
    i++;
    for (i; lst[i].next != 0; i++)
        ;
    lst->next = &lst[i];
    lst->next->x = x;
    lst->next->y = y;
    lst->next->next = 0;
    return;
}
if (lst->next->x < x || (lst->x == x && lst->next->y < y))
{
    add_list(lst->next, x, y);
    return;
}
if (lst->next->x > x || (lst->next->x == x && lst->next->y > y))
{
    for (i = 0; lst[i].next != 0; i++)
        ;
    i++;
    for (i; lst[i].next != 0; i++)
        ;
    lst[i].x = x;
    lst[i].y = y;
    lst[i].next = lst->next;
    lst->next = &lst[i];
    return;
}

}

int main(void)
{
int n, i, x, y;
llst lst[100000];
llst *temp;

scanf("%d", &n);
for (i = 0; i < n; i++)
{
    scanf("%d %d", &x, &y);
    add_list(lst, x, y);
}
temp = lst;
while (temp->next != 0)
{
    printf("%d %d\n", temp->next->x, temp->next->y);
    temp = temp->next;
}
return (0);

}

이렇게 짰는데 메모리는 괜찮았는데 이번에는 다시 시간 초과가 됐다.
시간 복잡도를 낮춰야 하는데 방법을 모르겠다.
내일 다시 고민해 봐야겠다.