[C++] 프로그래머스 - 문자열 내림차순 정렬하기 (sort 함수의 인자와 STL의 구조적 이해)

최근 코딩 테스트 문제를 풀던 중, 문자열을 내림차순으로 정렬하는 과정에서 겪은 컴파일 에러와 이를 해결하며 공부한 C++ STL의 이론적 배경을 정리해 보고자 합니다.

처음에는 단순히 '첫 번째 글자부터 마지막 글자까지 정렬하면 되겠지'라는 생각으로 다음과 같이 코드를 작성했습니다.

❌ 컴파일 에러가 발생한 초기 코드

C++

 

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

using namespace std;

string solution(string s) {
    // 컴파일 에러 및 런타임 에러 발생
    sort(s[0], s[s.size()]);
    
    return s;
}

의도와 달리 이 코드는 컴파일 에러를 유발하며, s[s.size()] 역시 문자열의 인덱스 범위를 벗어난 매우 위험한 접근이었습니다. 왜 이런 에러가 발생했는지, 그리고 올바른 해결 방법은 무엇인지 알아보았습니다.

1. 에러의 원인: std::sort가 요구하는 인자

C++ 표준 라이브러리의 std::sort 함수는 정렬할 범위를 지정할 때 데이터 값 자체(char)가 아닌, 데이터가 위치한 주소 값(반복자, Iterator)을 요구합니다.

제가 작성한 s[0]은 문자열의 첫 번째 '문자 데이터' 자체를 의미하므로 sort 함수의 인자로 적합하지 않았던 것입니다. C++에서 컨테이너의 시작 위치와 끝 위치를 올바르게 전달하려면 begin()과 end()를 사용해야 합니다.

• s.begin(): 문자열의 첫 번째 글자 위치를 가리키는 반복자
• s.end(): 문자열의 맨 마지막 글자 '다음' 위치를 가리키는 반복자

2. 올바른 해결 방법: 내림차순 정렬 구현

문자열을 큰 글자부터 작은 글자 순서(내림차순)로 정렬하는 방법은 크게 두 가지가 있습니다.

방법 A. greater<char>() 조건자 활용 (권장)

sort 함수의 세 번째 인자에 정렬 기준인 greater<char>()를 전달하면, 기본 오름차순이 아닌 내림차순으로 정렬이 수행됩니다.

C++

 

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

using namespace std;

string solution(string s) {
    // 시작과 끝 주소를 지정하고, 내림차순 옵션을 추가합니다.
    sort(s.begin(), s.end(), greater<char>());
    return s;
}

방법 B. 역반복자(rbegin, rend) 활용

begin() 대신 역방향(Reverse)을 의미하는 rbegin()과 rend()를 사용하면, 문자열을 뒤에서부터 거꾸로 역방향 정렬을 진행하므로 자연스럽게 내림차순 결과물을 얻을 수 있습니다.

C++

 

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

using namespace std;

string solution(string s) {
    // 역방향 반복자를 사용하여 뒤에서부터 정렬합니다.
    sort(s.rbegin(), s.rend());
    return s;
}

💡 이론적 고찰: std::string과 std::vector의 공통점

문제를 해결하는 과정에서 std::string을 정렬하는 문법이 std::vector를 정렬할 때와 완벽히 일치한다는 점에 주목했습니다. 이는 C++ STL(Standard Template Library)의 핵심 설계 철학인 직교성(Orthogonality) 덕분입니다.

C++ STL은 자료구조(컨테이너)와 알고리즘(sort 등)을 완전히 독립적으로 분리하여 설계했습니다. sort 함수는 대상이 벡터인지 문자열인지 알 필요가 없으며, 오직 앞뒤로 자유롭게 이동할 수 있는 주소인 '임의 접근 반복자'만 주어지면 정렬을 수행할 수 있도록 일반화(Generic)되어 있습니다.

두 컨테이너 모두 메모리가 쪼개지지 않고 한 줄로 예쁘게 서 있기 때문에, 배열의 인덱스 접근([ ] 연산자)이 $O(1)$로 가능하며, sort 알고리즘이 요구하는 강력한 반복자(Random Access)를 완벽하게 지원할 수 있는 것입니다.

✍️ 요약

1. std::string과 std::vector는 둘 다 메모리가 연속적으로 배치된 동적 배열 구조입니다.
2. 따라서 둘 다 앞뒤로 자유롭게 이동할 수 있는 포인터와 유사한 임의 접근 반복자(Iterator)를 제공합니다.
3. C++의 std::sort는 컨테이너의 종류와 상관없이 이 반복자만 있으면 작동하도록 일반화(Generic)되어 있기 때문에, 똑같은 문법으로 정렬이 가능합니다.

단순히 에러를 해결하는 것에 그치지 않고, 내부 작동 원리와 STL의 인터페이스 구조를 깊이 있게 이해할 수 있었던 유익한 경험이었습니다.