[프로그래머스] 문자열 내 마음대로 정렬하기 (Lv.1)

---

문제 링크

---

프로그래머스 - 문자열 내 마음대로 정렬하기

문제 설명

---

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

제한사항

• strings는 길이 1 이상, 50 이하인 배열입니다.
• strings의 원소는 소문자 알파벳으로 이루어져 있습니다.
• strings의 원소는 길이 1 이상, 100 이하인 문자열입니다.
• 모든 strings의 원소의 길이는 n보다 큽니다.
• 인덱스 n의 문자가 같은 경우 사전순으로 앞선 문자열이 앞쪽에 위치합니다.

내 풀이

---

sort에 람다를 넘겨 커스텀 정렬을 구현한다. 각 문자열의 n번째 문자(a[n], b[n])를 기준으로 비교하고, n번째 문자가 같을 경우 문자열 전체를 사전순(a < b)으로 비교한다.

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

using namespace std;

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

시간복잡도 분석

---

• sort: O(N log N), N = strings의 크기 (최대 50)
• 비교 함수: a[n] != b[n] 비교는 O(1), 같을 때 a < b는 문자열 길이만큼 O(L) (최대 100)
• 전체: O(N log N × L)

N ≤ 50, L ≤ 100이므로 최대 약 30,000번 연산 → 충분히 통과 가능하다.

후기

---

저번에 한 번 풀었던 문제라 조금 기억에 남아있었다. 오픈북을 한 기분…

• algorithm
• codingtest
• sort