[백준/C++] 1181번: 단어 정렬 - 직접 구현에서 STL(sort, Lambda)로 진화하기

1. 문제 분석

• 문제 번호: 1181번 (단어 정렬)
• 목표: 알파벳 소문자로 된 단어 N개를 아래 조건대로 정렬하라.
  1. 길이가 짧은 것부터
  2. 길이가 같으면 사전 순으로
  3. 단, 중복된 단어는 하나만 남기고 제거한다.

 

2. 첫 번째 시도: 

처음에는 라이브러리의 힘을 빌리지 않고, 직접 정렬 로직을 짜보려고 시도했다.

❌ 초기 코드의 한계

1. 복잡한 로직: 길이 정렬 따로, 사전 순 정렬 따로 구현하려니 반복문이 중첩되고 코드가 길어졌다.
2. 인덱스 오류 (Out of Bounds): 배열의 인덱스를 직접 다루다 보니 words[j+1] 참조 시 범위를 벗어나는 실수가 잦았다.
3. 효율성 문제: 직접 짠 버블 정렬 방식은 시간 복잡도가 O(N^2)이라 데이터가 많아지면 시간 초과가 발생한다.

 

 

 

3. 두 번째 시도: STL과 람다(Lambda) 이용

문제를 해결하기 위해 C++ STL의 sort와 find를 활용하는 방식으로 코드를 전면 수정했다.

 

✅ 최종 코드

#include <iostream>
#include <vector>
#include <algorithm> // sort, find 사용

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<string> words;
    
    // 1. 입력 및 중복 제거
    for (int i = 0; i < n; i++){
        string word;
        cin >> word;
        
        // 벡터에 해당 단어가 없을 때만 push_back (중복 방지)
        if(find(words.begin(), words.end(), word) == words.end()){
            words.push_back(word);
        }
    }
    
    // 2. 정렬 (람다식 활용: 커스텀 비교 함수)
    sort(words.begin(), words.end(), [](const string &a, const string &b) {
        // 길이가 같으면 사전 순으로 (오름차순)
        if (a.size() == b.size()) {
            return a < b;
        }
        // 길이가 다르면 짧은 순으로
        return a.size() < b.size();
    });

    // 3. 출력
    for(const string &w : words){
        cout << w << '\n';
    }
    
    return 0;
}

 

 

 

4. 깊이 있게 배운 개념들 (TIL) ✍️

 

① 중복 제거: Set vs Vector + Find

처음엔 Set을 쓸까 고민했다. (Set은 중복을 자동으로 제거해주잖아!)

하지만 Set은 순서가 없기 때문에 순서를 내가 제어할 수 있는 Vector에 find를 조합해서 사용했다.

find 함수 개념:

• find는 값을 찾으면 그 위치의 Iterator를 반환하고,
• find(begin, end, value): 범위 내에서 값을 찾는다. 못 찾으면 end()를 반환한다.

여기서 벡터와 iterator 개념을 알게되었다.

 

벡터 개념: 

 

(그림 출처: cppreference vector begin, end)

벡터의 마지막은 비어있다. 

 

iterator 개념:

 

공부해보니 Iterator는 포인터와 거의 똑같이 동작한다는 점을 깨달았다.

 

• 포인터처럼 *iter를 쓰면 그 안의 값을 꺼낼 수 있다. (Dereference)
• 포인터처럼 iter++를 하면 다음 칸으로 이동한다.
• 즉, Iterator는 **"컨테이너(Vector 등)의 원소를 가리키는 똑똑한 포인터 객체"**라고 이해하면 된다.

---

 

그렇다면 왜 벡터에서는 굳이 iterator를 만들어서 쓰는 것일까? 라는 질문이 생겼다. 

 

결론부터 말하면 모든 자료구조를 똑같은 방법으로 다루기 위해서 이다. 

포인터는 물리적인 메모리 주소를 이동하지만, iterator는 논리적인 다음 순서를 이동한다. 

1. 포인터의 한계: "옆집이 정말 다음 집일까?"

포인터는 메모리 주소를 다룹니다. ptr++ (포인터 1 증가)는 "메모리 상에서 바로 옆 칸으로 이동해라"라는 뜻이죠.

• 배열(Array)이나 벡터(Vector): 데이터가 메모리에 나란히 붙어 있습니다. 그래서 ptr++ 하면 진짜 다음 데이터가 나옵니다. 여기선 포인터가 완벽하게 작동합니다.
• 리스트(List)나 맵(Map, Tree): 데이터가 메모리 여기저기에 흩어져 있습니다. 서로 화살표(주소)로 연결만 되어 있죠. 여기서 포인터에 ++를 하면? **전혀 엉뚱한 메모리(쓰레기 값)를 가리키게 됩니다.

위 그림을 보면:

• Array (Vector): 기차처럼 칸이 붙어 있습니다. 옆으로 가면 다음 칸입니다.
• Linked List: 보물찾기 쪽지 같습니다. 다음 보물은 저~기 멀리 떨어져 있고, 쪽지(주소)를 봐야만 찾아갈 수 있습니다. 단순히 몸만 옆으로 이동해서는 찾을 수 없죠.

 

2. 이터레이터의 마법: "다음이 어디든 내가 찾아줄게"

이터레이터는 "똑똑한 포인터"입니다. 겉보기엔 포인터처럼 ++ 연산자를 쓰지만, 내부적으로는 자료구조에 맞춰서 다르게 행동합니다.

• 벡터 이터레이터의 ++: "메모리 한 칸 옆으로 가." (포인터랑 같음)
• 리스트 이터레이터의 ++: "다음 노드가 가리키는 주소를 찾아서 점프해." (포인터와 다름)
• 맵(트리) 이터레이터의 ++: "오른쪽 자식 노드로 가거나, 없으면 부모 노드를 타고 올라가." (훨씬 복잡함)

즉, 사용자인 우리는 내부 구조가 어떻게 생겼든 상관없이 ++만 하면 무조건 "논리적인 다음 순서"로 이동시켜 줍니다.

 

 

3. 왜 이게 중요할까? (일관성)

이 덕분에 algorithm 헤더에 있는 sort, find 같은 함수 하나로 모든 자료구조를 처리할 수 있게 됩니다.

만약 이터레이터가 없었다면? 우리는 함수를 이렇게 따로따로 만들어야 했을 겁니다.

• find_in_array(...)
• find_in_linked_list(...)
• find_in_tree(...)

하지만 이터레이터 덕분에 딱 하나만 있으면 됩니다.

// 벡터든, 리스트든, 셋이든 다 똑같이 쓴다!
find(v.begin(), v.end(), 3); 

 

 

---

 

② std::sort와 람다(Lambda) 식

sort 함수는 기본적으로 오름차순 정렬이지만, 비교 함수(Comparator)를 넣어주면 내 마음대로 정렬 기준을 바꿀 수 있다. 이때 람다(Lambda)를 쓰면 함수를 따로 선언할 필요 없이 즉석에서 만들 수 있다.

C++

 

// 람다 문법: [캡처](매개변수) { 본문 }
[](const string &a, const string &b) {
    if (a.size() == b.size()) return a < b; // 길이 같으면 사전 순
    return a.size() < b.size();             // 길이 다르면 길이 순
}

• 반환값 (true/false):
  • true: a가 b보다 앞에 와야 한다.
  • false: a가 b보다 뒤에 와야 한다.

 

 

③ 복사 vs 참조(&) vs 포인터(*)

참조 &을 쓰는 이유: 복사 시간줄이기  

 

포인터는 주소값을 담는 변수라 nullptr이 될 수 있지만, 참조자는 반드시 원본이 있어야 한다. 단순히 값을 비교만 할 때는 참조자가 훨씬 직관적이다.

 

• 복사: 원본은 그대로, 새 변수에 값만 복사 → 수정해도 원본 영향 없음
• 참조(&): 원본을 직접 가리킴 → 수정하면 원본도 바뀜, 복사 비용 없음
• for (string w : words) → 복사
• for (auto &w : words) → 참조

 복사 vs 참조(&) vs 포인터(*)

 

정리:

 

방식	코드	설명	특징
값 복사	string a	데이터를 통째로 복사해서 전달	원본 안전하지만 느림 (메모리 낭비)
참조	string &a	원본에 별명을 붙여 직접 접근	빠름, 원본 수정 가능
상수 참조	const string &a	원본을 직접 보지만 수정은 금지	빠르고 안전함 (Best Practice)

 

 

④ Comparator(비교 함수)와 람다(Lambda)의 관계

1. Comparator란 무엇인가?

std::sort는 기본적으로 오름차순(1, 2, 3...)으로 정렬하지만, 우리가 원하는 복잡한 기준(길이 순 → 사전 순)으로 정렬하려면 Comparator(비교 함수)가 필요하다.

• 역할: 두 원소(a, b)를 비교해서 "누가 앞에 와야 하는지" 알려준다.
• 반환값 (bool):
  • true: a가 b보다 앞에 와야 한다. (순서 유지)
  • false: a가 b보다 뒤에 와야 한다. (순서 바꿈)

즉, sort 함수는 내부적으로 정렬을 수행하면서 이 Comparator를 수없이 호출하고, 그 true/false 결과에 따라 원소들의 자리를 바꾼다.

2. 두 가지 구현 방법 (일반 함수 vs 람다)

Comparator를 구현하는 방법은 크게 두 가지가 있는데, 이번 문제에서는 코드가 훨씬 간결해지는 람다(Lambda) 방식을 선택했다.

A. 일반 함수로 정의하는 방법 전통적인 방식으로, 외부에 함수를 따로 만들어서 그 함수의 이름(포인터)을 sort에 전달한다.

// 1. 비교 함수를 따로 정의함
bool compare(const string &a, const string &b) {
    if (a.size() == b.size()) return a < b; // 길이 같으면 사전순
    return a.size() < b.size();             // 길이 다르면 길이순
}

// 2. sort에 함수 이름만 전달
sort(words.begin(), words.end(), compare);

 

B. 람다(Lambda)로 정의하는 방법 (내 코드) 함수 이름을 굳이 지을 필요 없이, sort 함수 안에서 즉석으로 비교 로직을 작성한다.

sort(words.begin(), words.end(), [](const string &a, const string &b) {
    if (a.size() == b.size()) return a < b;
    return a.size() < b.size();
});

• [](...): 람다의 시작. (Comparator 역할 시작)
• { ... }: 비교 규칙 작성.
• 장점: 코드가 짧아지고, 정렬 로직이 sort 바로 안에 있어서 읽기 편하다. (함수 정의를 찾아 위아래로 왔다 갔다 할 필요가 없다.)

 

---

5. 내가 깨달은 std::sort의 매력 ✨

직접 정렬을 구현하다가 sort를 써보니 신세계였다.

1. 비교 함수만 정의하면 끝:

a랑 b를 정해서 sort 한다고 해서 2개만 정렬하면 문제가 되지 않을까? 생각했는데 sort 함수는 내부적으로 퀵 소트를 사용해서 적힌 조건대로 다시 재정렬을 실행한다고 했다. 따라서 문제가 되지 않았다. 

 

• 내부적으로 퀵 소트(Quick Sort) 등을 써서 sort가 알아서 한다. 나는 단지 "누가 앞에 와야 하는지" 규칙(Rule)만 알려주면 된다.

1. 람다와 함께 쓰면 깔끔하다:
   • 굳이 bool compare(...) 함수를 위에 따로 만들지 않아도, sort 괄호 안에 로직을 쏙 넣으니 코드가 한눈에 들어온다.
2. 복합 조건도 한 방에 해결:
   • "길이가 같으면 사전 순, 다르면 길이 순" 같은 복잡한 조건도 if문 두 줄이면 끝난다.
3. 성능 최적화는 자동으로:
   • 내가 짠 O(N^2) 버블 정렬보다, STL의 O(N log N) 정렬이 압도적으로 빠르다.

 

📝 마무리

이번 문제는 단순히 정렬을 구현하는 것을 넘어, C++다운 코딩(Modern C++)이 무엇인지 배우는 계기가 되었다. 특히 const string & 패턴과 lambda 사용법은 앞으로도 계속 써먹을 수 있을 것 같다!