[백준] 1181 단어 정렬

🆀 문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

단, 중복된 단어는 하나만 남기고 제거

---

🅰 나의 풀이

이 문제도 시간 제한이 걸려 있어서 Quick sort로 풀었고 이번에는 stdlib에 있는 `qsort` 함수를 사용했다.

int main() {
    int n;
    scanf("%d\n", &n);
    char** arr = malloc(sizeof(char*) * n);
    char buffer[51];

    for (int i=0; i<n; i++){
        scanf("%s", buffer);
        arr[i] = malloc(strlen(buffer) +1);
        strcpy(arr[i], buffer);
    }
    
    qsort(arr, n, sizeof(arr), compare);
    
    for (int i=0; i<n-1; i++){
        if (strcmp(arr[i], arr[i+1])!=0)
            printf("%s\n", arr[i]);
        free(arr[i]);
    }
    printf("%s\n", arr[n-1]);

    free(arr);
    return 0;
}

 

int compare(const void *a, const void *b) {
    if ((strlen(*(const char**) a) - strlen(*(const char**)b))==0)
        return strcmp(*(const char**) a, *(const char**) b);
    return strlen(*(const char**) a) - strlen(*(const char**)b);
}

 

 

 

풀면서 계속 막혔던

이유 1.

: `fgets(buffer, 51, stdin)`을 사용

`fgets( )` 함수는 개행문자를 포함하여 입력 받기 때문에 개행문자 제거가 필수적이다!

공백을 포함한 입력을 받거나 파일에서 줄 단위 읽어오기가 필요할 때 유용하다.

<프로그래밍 기초>와 <자료구조> 수업 때도 계속 어려워하던 문자열 입력 받기...ㅠ

https://wifiaircat.tistory.com/23

[C] 📥 입출력 함수

 

 

이유 2.

: `strlen(*(const char**)a))` 에서 포인터 이해 부족

1. a는 `const void*`이므로 먼저 `(const char**)a` 문자열 포인터로 캐스팅해야 함.
2. 그걸 `*`로 역참조하면 `char*`가 돼서 진짜 문자열을 얻을 수 있음.
3. 이후 `strlen( )`으로 길이 재기

`char** arr;`은 `char*` 의 배열

`arr[i]`는 `char*` 하나(문자열 가리키는 포인터)
`qsort( )`는 `arr[i]`의 주소를 `compare( )` 함수에 넘겨줌

`compare( )`에 들어오는 a, b는 `(void*)`라서 실제로는 `char**`(char* 의 주소)

 

이유 3.

: 인덱스에서 segmentation fault

정렬 후 프린트할 때 중복을 제거하는 코드에서 i와 i+1을 비교하려니까 segmentation fault가 계속 났었다.

가장 앞이나 뒤에서 예외 처리가 필요했다. 나는 뒤에서 하나의 요소를 따로 프린트했다.

 

항상 풀고 나면 별 것 아닌 것 같은데 풀 때는 뭐가 그렇게 어렵게 느껴지는지...ㅠ

---

 

🆂 다른 풀이

	char arr[20000][51] = { 0 };
	for (int i = 0; i < n; i++)
		scanf("%s", arr[i]);

 

단어 개수 2만 개, 단어 길이 50의 제한을 적극적으로 사용할 수 있다.

동적 할당을 안 하니까 코드가 굉장히 깔끔하고 쉬워지긴 한다.

 

	for (int i = 0; i < n; i++) {
		if (strcmp(arr[i], arr[i + 1]) != 0 || i == n - 1)
			printf("%s\n", arr[i]);
	}

정렬 후 프린트할 때 중복을 제거하는 코드에서 i와 i+1을 비교하려다 보니까 segmentation fault가 계속 났었다.

여기서는 i가 n -1이 되더라도 인덱스를 벗어나지 않고 or문에 걸리게 만들어 fault 없이 프린트했다.

---