특정 인덱스 기준 문자열 정렬하기 - 문자열 내 마음대로 정렬하기 (12915)

문제 설명

문자열로 구성된 리스트 strings와 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 문자를 기준으로 오름차순 정렬하는 문제입니다.

예를 들어 strings = ["sun", "bed", "car"]이고 n = 1이라면, 각 단어의 인덱스 1의 문자는 "u", "e", "a"입니다. 이를 기준으로 정렬하면 ["car", "bed", "sun"]이 됩니다.

제한 조건

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

입출력 예

strings n return

["sun", "bed", "car"]	1	["car", "bed", "sun"]
["abce", "abcd", "cdx"]	2	["abcd", "abce", "cdx"]

---

문제 해결 과정

이 문제를 보고 처음 떠올린 접근법은 strings[i][n]을 활용하여 정렬하는 것이었습니다. 먼저, 각 문자열에서 n번째 문자를 기준으로 정렬하면 된다고 생각했습니다. sort 함수가 알파벳을 정렬할 수 있다는 점을 이용하면, strings[i][n]을 정렬 기준으로 설정하여 손쉽게 해결할 수 있을 것이라 예상했습니다. 찾아보니 sort 함수를 사용하면 알파벳도 오름차순 정렬이 가능하다는 점을 발견했습니다. 이를 이용해 strings[i][n]을 맨 앞으로 이동시켜 정렬하면 쉽게 해결할 수 있을 것이라고 생각했습니다.

초기 접근 방식

1. 만약 n == 0이면, 단순히 사전순으로 정렬 후 반환하면 된다.
2. strings[i][n]과 strings[i][0]을 교환하는 방식으로 strings[i][n]을 맨 앞으로 배치하려 했다.
3. 하지만, 이렇게 하면 같은 n번째 문자를 가진 문자열들의 원래 순서가 유지되지 않아 문제의 조건을 만족하지 못함을 깨달았다. 예를 들어, strings = ["abc", "acd", "abf"]이고 n = 1이라면, n번째 문자가 모두 b인 경우에도 원래의 사전순이 유지되어야 하지만, 단순히 strings[i][n]과 strings[i][0]을 교환하면 이를 보장할 수 없게 된다. 따라서 정렬 과정에서 원래의 순서를 유지하는 방법을 고민해야 했다.

개선된 해결책

• strings[i][n]을 strings[i]의 맨 앞에 추가한 후 정렬하고, 정렬이 끝난 후 제거하는 방식으로 해결했다.
• 이 방법을 사용하면 정렬 기준이 n번째 문자가 되고, 동일한 문자일 경우 원래의 사전순 정렬이 유지된다.

---

내 정답 코드 (C++)

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

using namespace std;

vector<string> solution(vector<string> strings, int n) {
    // 만약 n이 0이면 바로 정렬 후 반환
    if (n == 0) {
        sort(strings.begin(), strings.end());
        return strings;
    }
    
    // 각 문자열의 n번째 문자를 맨 앞에 추가
    for (string &s : strings) {
        s.insert(0, 1, s[n]);
    }
    
    // 정렬 수행
    sort(strings.begin(), strings.end());
    
    // 추가한 문자 제거
    for (string &s : strings) {
        s.erase(0, 1);
    }
    
    return strings;
}

코드 설명

1. n == 0인 경우, 바로 사전순 정렬을 수행.
2. 각 문자열의 n번째 문자를 맨 앞에 추가하여 정렬 기준으로 활용하면, 정렬 시 n번째 문자가 우선적으로 비교되므로 원하는 순서를 보장할 수 있습니다. 이후 정렬이 끝난 후 해당 문자를 제거하면 원래의 문자열을 유지하면서도 정렬이 가능합니다.
3. 정렬 수행.
4. 정렬이 끝난 후 앞에 추가했던 문자를 제거하여 원래 문자열로 복구.

---

최적화된 코드 (C++)

#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) {
        return (a[n] == b[n]) ? a < b : a[n] < b[n];
    });
    return strings;
}

최적화된 코드 설명

• sort 함수의 사용자 정의 비교 함수(lambda function)를 사용하여 정렬 기준을 직접 지정하면, 기존 sort 함수의 기본 정렬 방식보다 더 유연하게 기준을 설정할 수 있습니다. lambda function을 활용하면 n번째 문자를 우선적으로 비교하고, 동일한 경우 전체 문자열을 비교하여 사전순 정렬이 이루어집니다. 이 방식은 문자열을 수정하는 방법보다 공간 복잡도가 낮아 더 효율적입니다.
• 첫 번째 기준: n번째 문자를 비교하여 정렬.
• 두 번째 기준: n번째 문자가 같을 경우, 전체 문자열을 사전순 정렬.
• 공간 복잡도 감소: 문자열을 수정하지 않고 직접 비교하여 정렬하므로 메모리 절약 가능.

---

결론

초기 접근 방식에서 strings[i][n]을 맨 앞에 추가하고 정렬한 후 제거하는 방법을 사용했으나, 더 나은 해결책으로 lambda function을 활용하여 sort의 비교 기준을 설정하는 방법을 찾았습니다. 이 방법을 사용하면 더 직관적이고 메모리 효율적인 코드 작성이 가능합니다. lambda function을 활용하면 문자열을 수정하지 않고 정렬할 수 있어 추가적인 메모리 할당이 필요하지 않습니다. 반면, 문자열을 조작하는 방식은 원본 문자열을 변경하거나 추가적인 저장 공간을 요구할 수 있어 비효율적입니다.