백준 26265번 [멘토와 멘티](C++) -yes6686- 티스토리

백준 문제 풀이: 26265 (멘토와 멘티)

---

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

문제 설명:

멘토와 멘티의 이름 리스트가 주어집니다. 멘토와 멘티의 관계를 정렬하는 규칙은 다음과 같습니다:

1. 멘토의 이름을 기준으로 오름차순 정렬합니다.
2. 멘토 이름이 같다면, 멘티의 이름을 기준으로 내림차순 정렬합니다.

이 정렬 규칙에 따라 멘토와 멘티의 리스트를 출력하는 프로그램을 작성하세요.

---

문제 해결 코드

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

// 멘토와 멘티 정보를 저장하는 배열
pair<string, string> arr[100001];

// 비교 함수
bool compare(pair<string, string> a, pair<string, string> b) {
    if (a.first == b.first) {
        return a.second > b.second; // 멘티 이름은 내림차순
    }
    return a.first < b.first; // 멘토 이름은 오름차순
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n; // 멘토-멘티 쌍의 수
    cin >> n;

    // 입력 받기
    for (int i = 0; i < n; i++) {
        cin >> arr[i].first >> arr[i].second;
    }

    // 정렬
    sort(arr, arr + n, compare);

    // 출력
    for (int i = 0; i < n; i++) {
        cout << arr[i].first << ' ' << arr[i].second << '\n';
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 멘토와 멘티를 저장한 배열을 사용자 정의 비교 함수를 사용하여 정렬합니다.
• 구현 세부사항:
  • pair<string, string> arr[100001]: 멘토와 멘티 이름을 각각 저장합니다.
  • compare 함수: 멘토 이름은 오름차순, 멘티 이름은 내림차순으로 정렬합니다.
  • sort(arr, arr + n, compare): STL sort 함수를 사용해 사용자 정의 정렬 규칙을 적용합니다.
• 시간 복잡도 분석:
  • 정렬의 시간 복잡도는 O(n log n)입니다.
  • 입력과 출력은 O(n)입니다.
  • 전체 시간 복잡도는 O(n log n)입니다.

---

결과

멘토와 멘티의 이름 리스트를 주어진 정렬 규칙에 따라 정확히 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!