[BaekJoon/백준] 11650번 & 나중에 다시보기

C언어로 이 문제를 푸는 데 꽤 오랜 시간이 걸렸다.

 

값의 쌍에 대한 문제이다 보니, 배열보다는 다른 방법이 더 좋겠지만

Collection이나 Map 같은 계열을 사용하지 않고, 배열로 풀려고 했다.

 

정말 솔직하게 3시간이나 걸렸다.

 

처음엔 안정적인 알고리즘을 이용하여 풀어야된다고 생각했다.

"안정적인 알고리즘의 특징을 통해 뒤에꺼 먼저 정렬한 뒤 앞에꺼 정렬하면 될 것" 이라고 생각했으나, 생각해보니 안정적일 필욘 없다.

위치가 같은 두 점이 없을 뿐더러, 있더라도 순서가 바뀌는게 출력값 표현에는 변화가 없으므로..

 

따라서 표준 라이브러리에서 제공하는 qsort 함수를 사용했다. 이 함수를 직접 구현해본 기억도 있고, 사용해본 기억도 있지만

아직까지도 너무 헷갈린 듯 하다. qsort 사용에 대해 메모리 참조 과정이 너무 헷갈려서 그림을 그려 해결했다.

 

기초개념

증명1

증명2 / a의 인덱스 0,0부터 시작인데 실수.. ㅎㅎ

증명3/"메모리 구조가 다르다"

 실험
 1.
 char a[20000][50];
 
 printf("%ld", sizeof(a[0]));
 
 Output : 50 (a[0]의 주소의 메모리 크기 50)
 
 
 2.
 char **a;
 
 a = (char **)calloc(nx, sizeof(char *));
 for(int i = 0; i < nx; i++) {
     a[i] = (char *)calloc(50, sizeof(char));
 }

 
 printf("%ld", sizeof(a[0]));

 Output : 8 (char *형 변수 a[0]이 담고 있는 공간의 크기 8) // sizeof(char *) = 8

 

이중 포인터 참고 : dojang.io/mod/page/view.php?id=319

 

역시 그림을 그리는 게 이해하는 데에 수월하고 빠르다.

 

 

참고로 qsort를 사용하여 문제를 풀기 전에, 카운팅 정렬을 직접 구현하여 풀려고 하는 다소 멍청한 시간을 보냈다. 또는 퀵소트를 직접 구현하기도 했다. 이 두 방법이 먹히지 못하는 이유는 당연하다. '메모리의 교환'이 아니라 '값의 교환'이므로, 두 쌍을 이룬 값이 그대로 움직이지 않고 따로 놀게 된다는 것이다. 두 방법 다 '값의 교환'이 아닌 '메모리의 교환' 방식으로 구현했으면 풀긴 했을텐데... 바보같았다.

 

 

제출한 코드

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

int compa(int **a, int **b) {
    int x = **a;
    int y = **b;
    
    if(x < y)
        return -1;
    else if(x > y)
        return 1;
    else
        return 0;
}

int compa2(int **a, int **b) {
    int x = *(*a+1);
    int y = *(*b+1);
    
    if(x < y)
        return -1;
    else if(x > y)
        return 1;
    else
        return 0;
}

int main() {
    int **x;
    int nx;
    
    scanf("%d", &nx);
    
    x = (int**)calloc(nx, sizeof(int *));
    for(int i = 0; i < nx; i++) {
        x[i] = (int *)calloc(2, sizeof(int));
    }
    
    for(int i = 0; i < nx; i ++ ){
        scanf("%d %d", &x[i][0], &x[i][1]);
    }

    
    qsort(x, nx, (sizeof(int))*2,  (int(*)(const void *, const void *))compa2);
    qsort(x, nx, (sizeof(int))*2,  (int(*)(const void *, const void *))compa);
    
    
    for(int i = 0; i < nx; i ++ ){
        printf("%d %d\n", x[i][0], x[i][1]);
    }
}

끝.. 해야할 일들이 많은데 이거에 3시간 보낸 현타가 밀려온다..