[SISS/C언어 스터디] 25-1학기 1주차 스터디 - 정렬, 추가 과제

[SISS/C언어 스터디] 25-1학기 1주차 스터디 - 정렬, 추가 과제

: 1주차 (3/10~3/16) 프로그래머스 지정 1문제 (정렬)
https://school.programmers.co.kr/learn/courses/30/lessons/42746
 

정렬 - 가장 큰 수

---

풀이 인증 화면 캡쳐

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

int compare(const void *a, const void *b)
{
    char str_a[10], str_b[10];

		// 테스트케이스 예시의(30, 3) 앞자리 숫자끼리 비교하였을 경우 생기는 문제를 해결하기 위해 각각의 숫자가 아닌 두 숫자를 연결하여 비교 진행
    sprintf(str_a, "%d%d", *(int *)a, *(int *)b);
    sprintf(str_b, "%d%d", *(int *)b, *(int *)a);

    return strcmp(str_b, str_a);
}

void my_sort(int *numbers, int numbers_len)
{
		// qsort()의 기준으로 compare 이용
    qsort(numbers, numbers_len, sizeof(int), compare);
}

char *solution(int numbers[], size_t numbers_len)
{
    char *answer = (char *)malloc(sizeof(char) * 4 * numbers_len);
    int cnt = 0;
    answer[0] = '\0';

		// 정렬
    my_sort(numbers, numbers_len);

    for (int i = 0; i < numbers_len; i++)
    {
        char buffer[5];
        sprintf(buffer, "%d", numbers[i]);
        strcat(answer, buffer);  // 숫자 연결
    }

    if (answer[0] == '0')
        answer[1] = '\0';

    answer = (char *)realloc(answer, sizeof(char) * (strlen(answer) + 1));

    return answer;
}

 

24542

---

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

#define MOD 1000000007

// 벡터 정의
typedef struct {
    int *data;
    int size;
    int capacity;
} Vector;

// 벡터 초기화
void initVector(Vector *v) {
    v->size = 0;
    v->capacity = 10;
    v->data = (int *)malloc(v->capacity * sizeof(int));
}

// 벡터 값 추가
void pushBack(Vector *v, int value) {
    if (v->size >= v->capacity) {
        v->capacity *= 2;
        v->data = (int *)realloc(v->data, v->capacity * sizeof(int));
    }
    v->data[v->size++] = value;
}

// 벡터 메모리 해제
void freeVector(Vector *v) {
    free(v->data);
}

// bfs
int bfs(int x, int *visit, Vector *graph, int N) {
    int *queue = (int *)malloc(N * sizeof(int));
    int front = 0, rear = 0;
    queue[rear++] = x;
    visit[x] = 1;
    int number = 1;

    while (front < rear) {
        int cur = queue[front++];
        for (int i = 0; i < graph[cur].size; i++) {
            int nxt = graph[cur].data[i];
            if (!visit[nxt]) {
                queue[rear++] = nxt;
                visit[nxt] = 1;
                number++;
            }
        }
    }

    free(queue);
    return number;
}

int main() {
    int N, M;
    scanf("%d %d", &N, &M);

		// 배열 할당
    Vector *graph = (Vector *)malloc((N + 1) * sizeof(Vector));
    for (int i = 0; i <= N; i++) {
        initVector(&graph[i]);
    }

    int *visit = (int *)calloc(N + 1, sizeof(int));
    long long answer = 1;

    // 입력
    for (int i = 0; i < M; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        pushBack(&graph[u], v);
        pushBack(&graph[v], u);
    }

    // 각 요소 bfs 통해 크기 계산
    for (int v = 1; v <= N; ++v) {
        if (!visit[v]) {
            answer = (answer * bfs(v, visit, graph, N)) % MOD;
        }
    }

	// 출력
    printf("%lld\n", answer);

    // 메모리 해제
    for (int i = 0; i <= N; i++) {
        freeVector(&graph[i]);
    }
    
    free(graph);
    free(visit);

    return 0;
}