선밥의 공부하는 블로그

문자열 내 마음대로 정렬하기Permalink

문제 링크Permalink

문자열 내 마음대로 정렬하기

분석Permalink

문자열을 정렬하는 문제입니다.

C++ std::sort함수의 정렬 기준을 변경해 정렬 할 수 있습니다.

혹은 정렬 알고리즘을 직접 구현하고, 값이 같은 경우의 처리를 추가로 구현해서 풀 수 있습니다.

풀이Permalink

std::sort를 사용한 방법입니다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> solution(vector<string> strings, int n) {
    vector<string> answer{ strings };
    
    sort(answer.begin(), answer.end(), [n](const string& a, const string& b)
        { return (a[n] == b[n]) ? a < b : a[n] < b[n]; });
    
    return answer;
}

람다 함수를 사용해 정렬 기준을 정해주었습니다.

병합 정렬을 직접 구현해 푼 방법입니다.

#include <string>
#include <vector>

using namespace std;

void merge(vector<string>& strings, int left, int mid, int right, int n)
{
    vector<string> temp(right - left + 1);
    
    int i = left;
    int j = mid + 1;
    int k = 0;
    
    while (i <= mid && j <= right)
    {
        if (strings[i][n] < strings[j][n])
        {
            temp[k++] = strings[i++];
        }
        else if (strings[i][n] > strings[j][n])
        {
            temp[k++] = strings[j++];
        }
        else
        {
            if (strings[i] < strings[j])
            {
                temp[k++] = strings[i++];
            }
            else
            {
                temp[k++] = strings[j++];
            }
        }
    }
    
    while (i <= mid)
    {
        temp[k++] = strings[i++];
    }
    while (j <= right)
    {
        temp[k++] = strings[j++];
    }
    
    for (int l = 0; l < temp.size(); ++l)
    {
        strings[left + l] = temp[l];
    }
}

void mergeSort(vector<string>& strings, int left, int right, int n)
{
    if (left >= right)
    {
        return;
    }
    
    int mid = left + (right - left) / 2;
    mergeSort(strings, left, mid, n);
    mergeSort(strings, mid + 1, right, n);
    merge(strings, left, mid, right, n);
}

vector<string> solution(vector<string> strings, int n) {
    vector<string> answer { strings };
    
    mergeSort(answer, 0, answer.size() - 1, n);
    
    return answer;
}

merge함수에서 값을 확인해 정렬한 상태로 배열을 병합합니다.

mergeSort함수에서는 배열을 분리하고, 정렬하는 함수를 호출합니다.

일반적인 병합 정렬과 다른 점은 n번째 문자를 기준으로 정렬하므로 함수에 n에 대한 매개변수를 추가로 받습니다.
n번째 문자가 같을경우 문자열을 사전순으로 정렬해야하므로, 다음과 같은 코드가 추가됩니다.

else
{
    if (strings[i] < strings[j])
    {
        temp[k++] = strings[i++];
    }
    else
    {
        temp[k++] = strings[j++];
    }
}

해당 코드에서 n번째의 문자가 같을 경우 전체 문자열을 비교합니다.

성능 요약Permalink

테스트 1 〉 통과 (0.01ms, 3.62MB)
테스트 2 〉 통과 (0.01ms, 3.62MB)
테스트 3 〉 통과 (0.02ms, 4.18MB)
테스트 4 〉 통과 (0.02ms, 4.19MB)
테스트 5 〉 통과 (0.01ms, 4.19MB)
테스트 6 〉 통과 (0.03ms, 4.16MB)
테스트 7 〉 통과 (0.01ms, 4.12MB)
테스트 8 〉 통과 (0.02ms, 4.09MB)
테스트 9 〉 통과 (0.01ms, 4.14MB)
테스트 10 〉 통과 (0.03ms, 4.12MB)
테스트 11 〉 통과 (0.01ms, 4.2MB)
테스트 12 〉 통과 (0.04ms, 4.2MB)

병합 정렬을 구현해 푼 방법입니다.

테스트 1 〉 통과 (0.02ms, 3.68MB)
테스트 2 〉 통과 (0.01ms, 4.2MB)
테스트 3 〉 통과 (0.03ms, 3.64MB)
테스트 4 〉 통과 (0.03ms, 4.18MB)
테스트 5 〉 통과 (0.01ms, 4.26MB)
테스트 6 〉 통과 (0.05ms, 4.18MB)
테스트 7 〉 통과 (0.02ms, 4.2MB)
테스트 8 〉 통과 (0.03ms, 4.16MB)
테스트 9 〉 통과 (0.02ms, 4.13MB)
테스트 10 〉 통과 (0.05ms, 3.66MB)
테스트 11 〉 통과 (0.01ms, 3.66MB)
테스트 12 〉 통과 (0.06ms, 4.14MB)

Programmers 카테고리 내 다른 글 보러가기

댓글남기기

최근 글