반응형
728x90
반응형
 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제의 출처!

    • 문자열 내림차순으로 배치하기

설명

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

제한 사항

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

입출력 예

            s                                                                   return

"Zbcdefg" "gfedcbZ"

 

[ C++ ]

1
2
3
4
5
6
7
8
9
10
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
string solution(string s) {
    sort(s.begin(), s.end(), greater<>()); // 내림차순 : greater<> / 오름차순 : less<>
    return s;
}
cs

sort 함수의 세번째 인자로는 오름, 내림차순 혹은 정렬의 조건을 포함하는 함수를 넣을 수 있다. 

주석과 같이 greater / less 등의 임시 객체 함수로 내림차순과 오름차순을 정할 수 있다.

[ Python ]

1
2
3
4
5
def solution(s):
    return "".join(sorted(s, reverse=True))
    # sorted : s를 정렬하여 새로운 리스트를 반환. (list.sort는 내부 정렬을 함. 새로운 리스트를 반환하지 않음)
    # "".join() join 내의 리스트 요소들을 모두 합치는데, 앞의 문자나 문자열을 요소 중간마다 채움.
 
cs

sorted 함수와 리스트 내의 sort 함수의 차이점을 주석에 적었으며, join 의 사용법 또한 주석 처리 되어 있다.

728x90
반응형
728x90
반응형

 

오늘도 짤막하게 코딩해보고 바로 포스팅한다. 이렇게 하니 매우 여유있게 보고 정리할 수 있는 것 같아서 좋다.
선택 정렬 또한 간단하다 ㅋ

선택 정렬이란?

예시임

위와 같은 배열이 있다. 이를 오름차순으로 정렬할 예정이다.

버블 정렬이 이전 요소들 앞뒤를 비교해가면서 결국, 맨 마지막 대상을 확정 짓는 것이라면 선택 정렬은 반대이다.

맨 왼쪽 요소를 확정 지어가면서 범위를 좁혀나가는 것인데, 버블 정렬처럼 비교한 후 더 변경할 조건이 맞는 경우 값을 교환하는 것이 아니라 변경할 '인덱스'를 저장해 둔 후, 자리를 확정 지을 때 이 인덱스를 활용하여 교환을 한다.

일련의 프로세스 정리

!! 수정 !! :: 3번 동그라미에서 1(인덱스 2)1(인덱스 3)로 변경되어야 합니다!!!!!!!!!!!!!!!!!!!!!

코드 및 실행 결과

----

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
 
void SelectSort(int arr[], int n)
{
    int min_index = -1;
    int temp = -1;
 
    int i = 0, j = 0;
    for (i = 0; i < n-1; i++// 마지막에서 -1 인덱스까지만 확정 지으면 나머지 하나는 자동 확정~
    {
        min_index = i; // 오름차순이라는 가정 하에, 가장 작은 값이 존재하는 인덱스
        for (j = i+1; j < n; j++// 확정 지을 자리를 비교할 필요가 없으므로 i + 1
        {
            if (arr[min_index] > arr[j])
                min_index = j;
        }
        temp = arr[i];
        arr[i] = arr[min_index];
        arr[min_index] = temp;
    }
    return;
}
 
int main(void)
{
    int i = 0;
    int arr[4= { 5931 };
    SelectSort(arr, sizeof(arr) / sizeof(int));
    
    for (i = 0; i < 4; i++)
        printf("%d, ", arr[i]);
    fputc('\n', stdout);
    return 0;
}
cs

9번 라인에서 i의 조건을 n-1 미만으로 두는 이유를 다음 그림을 통해서 설명하겠다.

 

----

 

 

선택 정렬 성능

최악의 경우 비교 횟수 : (n-1) + (n-2) + ... + 2 + 1 -> O(n^2)
최악의 경우 대입 횟수 : n-1 회 무조건 대입이 일어난다. -> O(n)

버블 정렬에 비하면 양호하지만 버블 정렬에서는 최선의 경우에는 한 번도 대입 연산이 없을 수 있으므로, 비교하기 난감할 뿐이다.

728x90
반응형

+ Recent posts