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

문제 설명

문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱스 1의 문자 "u", "e", "a"로 strings를 정렬합니다.

 

문제 유형

• 사용자 정의 정렬
  • 문자열의 단순 크기 비교가 아닌 n번째 문자를 기준으로 정렬한다.

 

의사코드

1. 결과값을 저장할 변수(result)를 선언한다.
2. 알파벳별로 우선순위를 저장할 변수(v)를 선언한다.
3. [반복문] 입력받은 string 배열의 크기만큼 반복한다
   1. n번째 알파벳의 인덱스를 계산하여 변수(idx)에 저장한다.
   2. v 벡터의 인덱스(idx)에 해당 문자열을 추가한다.
4. [반복문] v의 크기만큼 반복한다.
   1. v의 요소인 priority_queue에 요소가 있는지 확인한다.
   2. 요소가 있다면 값을 꺼내어 result에 저장한다.
5. 결과값(result)를 반환한다.

 

코드 작성

#include <string>
#include <vector>
#include <queue>

using namespace std;

const int AlphabetLength = 26;

vector<string> solution(vector<string> strings, int n) {
    vector<string> result;
    vector<priority_queue<string, vector<string>, greater<string>>> v(AlphabetLength);
    
    for (string& str : strings)
    {
        int idx = str[n] - 'a';
        auto& pq = v[idx];
        pq.push(str);
    }
    
    for (auto& pq : v)
    {
        while (!pq.empty())
        {
            result.push_back(pq.top());
            pq.pop();
        }
    }
    
    return result;
}

 

 

다른 풀이

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int i;

bool compare (string a, string b) {
    return a[i] == b[i] ? a < b : a[i] < b[i];
}

vector<string> solution(vector<string> strings, int n) {
    i = n;
    sort (strings.begin(), strings.end(), compare);
    return strings;
}

• sort 함수의 compare를 활용하여 간단히 정리할 수 있다.
• 문자열 간의 대소 비교는 순서를 비교할 수 있다.