[프로그래머스 lv1] 버블정렬로 문자열 내림차순

프로그래머스 레벨1 문자열 내림차순으로 배치하기 문제입니다.

 

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

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

char* solution(const char* s) {
    int length = strlen(s);
    char* answer = (char*)malloc(length+1);
    strcpy(answer, s);
    char tmp = 0;
    
    for(int i=0; i<length-1; i++){
        for(int j=0; j<length-1-i; j++){
            if(answer[j] < answer[j+1]){
                tmp = answer[j];
                answer[j] = answer[j+1];
                answer[j+1] = tmp;
            }
        }
    }
    
    return answer;
}

 

* strcpy: 문자열을 복사하는 함수

char *strcpy(char* 대상문자열, char const* 원본문자열);

대상문자열의 포인터를 반환한다.

 

*버블정렬(bubble sort): 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

시간 복잡도 O(n^2)으로 상당히 느리지만 코드가 단순하다는 장점이 있다.

아래는 버블정렬의 의사코드이다.

 

procedure bubbleSort( A : list of sortable items ) defined as:
  for each i in 1 to length(A) do:
       for each j in length(A) downto i + 1 do:
         if A[ j ] < A[ j - 1 ] then
           swap( A[ j ],  A[ j - 1 ] )