백준 1181번 [단어 정렬](C++)-yes6686- 티스토리

백준 문제 풀이: 1181 [단어 정렬]

---

문제 링크: https://www.acmicpc.net/problem/1181

문제 설명:

알파벳 소문자로 이루어진 단어 n개가 주어질 때, 아래와 같은 조건으로 단어들을 정렬하는 프로그램을 작성하세요:

• 길이가 짧은 것부터
• 길이가 같다면 사전 순으로

중복된 단어는 한 번만 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std; 

bool compare(string a, string b) {
    if (a.length() == b.length()) {
        return a < b; // 사전 순으로 정렬
    } else {
        return a.length() < b.length(); // 길이 순으로 정렬
    }
}

int main() {
    int T;
    string n[20001];
    cin >> T;

    for (int i = 0; i < T; i++) {
        cin >> n[i];
    }

    sort(n, n + T, compare); // 사용자 정의 비교 함수를 이용한 정렬
    cout << n[0] << '\n'; // 첫 단어 출력

    for (int i = 1; i < T; i++) {
        if (n[i] != n[i - 1]) { // 중복 제거
            cout << n[i] << '\n';
        }
    }
}

---

코드 설명

• 핵심 아이디어: 단어의 길이와 사전 순서를 고려해 사용자 정의 비교 함수로 정렬합니다.
• 구현 세부사항:
  • 입력된 단어를 배열에 저장합니다.
  • sort 함수에 사용자 정의 비교 함수 compare를 전달해 정렬합니다.
  • 중복된 단어는 출력 시 제거합니다.
• 시간 복잡도: O(n log n)
  • 정렬 과정에서 O(n log n)
  • 중복 제거 및 출력 과정에서 O(n)

---

결과

입력된 단어를 조건에 맞게 정확히 정렬하며, 중복 없이 출력합니다. 최적화된 정렬 알고리즘을 활용하여 효율적으로 동작합니다.

다른 접근 방식이나 궁금한 점이 있다면 알려주세요!