[프로그래머스 level 1] 문자열 내림차순으로 배치하기

[출처 : 프로그래머스]

문제

문자열 s에 나타나는 문자를 큰 것부터 작은 순으로 정렬해 새로운 문자열을 리턴하는 함수, solution을 완성해주세요.
s는 영문 대소문자로만 구성되어 있으며, 대문자는 소문자보다 작은 것으로 간주합니다. 제한 사항

• str은 길이 1 이상인 문자열입니다.

 

 

---

풀이

- 나는 선택정렬을 사용하여 풀었다. 선택 정렬은 O(N^2)의 시간 복잡도. 그렇게 좋진 않다.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#define swap(x, y, temp)    ((temp=x), (x=y), (y=temp))

// 파라미터로 주어지는 문자열은 const로 주어집니다. 변경하려면 문자열을 복사해서 사용하세요.
char* solution(const char* s) {
    int n, max, i, j, temp;
    n = strlen(s);
    // return 값은 malloc 등 동적 할당을 사용해주세요. 할당 길이는 상황에 맞게 변경해주세요.
    char* answer = (char*)malloc(n*sizeof(char)+1);
    strcpy(answer, s);
    for(i=0; i<n-1; i++){
        max=i;
        for(j=i+1; j<n; j++){
            if(answer[max]<answer[j]) max=j;
        }
        if(max!=i)  swap(answer[max], answer[i], temp);
    }
    return answer;
}

 

찾아보니 퀵정렬을 사용하여 푼 사람도 있었는데, C언어 기본 라이브러리에서 퀵 정렬 함수가 있는 줄 처음 알았다.

 

- 퀵정렬 사용한 풀이 (퀵 정렬의 시간 복잡도는 평균 O(nlogn), 최악의 경우 O(N^2)

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
int compare(const void* fir, const void* sec){
    return  -strcmp((char*)fir, (char*)sec);
}
// 파라미터로 주어지는 문자열은 const로 주어집니다. 변경하려면 문자열을 복사해서 사용하세요.
char* solution(const char* s) {
    // return 값은 malloc 등 동적 할당을 사용해주세요. 할당 길이는 상황에 맞게 변경해주세요.
    char* answer = (char*)malloc(strlen(s)*sizeof(char));
    char temp[strlen(s)];
    strcpy(temp, s);
    qsort(temp, strlen(s), sizeof(char), compare);
    strcpy(answer, temp);
    return answer;
}

복잡하게 퀵정렬 직접 짜기보다 라이브러리 함수를 유용하게 잘 써야겠다.

compare의 인자에 대해서.

- compare함수는 문자열 비교 함수인 strcmp와 같은 모양을 띄고 있습니다. 따라서 문자열의 배열이라면, strcmpy 함수를 그대로 넣어 사용할 수도 있습니다. 오름차순(1 2 3..)으로 정렬하고 싶을 때, compare함수의 첫 번째 파라미터가 더 클 때 양수를 반환, 첫 번째 파라미터가 더 작을 때 음수를 반환, 같을 때 0을 반환하게 만들면 됩니다. (내림차순일 때는 반대로)

나는 내림차순이므로 strcmp(s1, s2)의 결과는 s1이 더 클 때 1을 반환하는 것을 이용하여 '-'를 붙였다.

---

* 개인적인 학습 목적으로 작성한 글이기에 내용에 잘못된 정보가 있을 수 있습니다.

* 문제 출처 - https://programmers.co.kr/learn/courses/30/lessons/12917