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

1. 문제 설명

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

 

- 제한 사항

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

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

string solution(string s) {
	int n = s.length();

	for (int i = 1; i < n; i++)
	{
		char key = s[i];
		int j = i - 1;

		while (j >= 0 && s[j] < key)
		{
			s[j + 1] = s[j];
			j--;
		}

		swap(s[j + 1], key);

	}

	return s;
}

 

3. 정리

문자들은 정렬 알고리즘(삽입정렬) 구현하여 정렬 하였다.

 

전체 시간 복잡도는 삽입 정렬의 시간 복잡도인 O(n²) 이다.

 

출처 :https://school.programmers.co.kr/learn/courses/30/lessons/12917