백준 2910번 [빈도 정렬](C++)-yes6686- 티스토리

백준 문제 풀이: 2910 [빈도 정렬]

---

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

문제 설명:

메시지의 빈도를 기준으로 내림차순으로 정렬한 뒤, 빈도가 같다면 먼저 입력된 메시지가 앞에 오도록 정렬하는 프로그램을 작성하세요.

입력 조건:

• 첫째 줄에 메시지의 개수 n과 메시지를 입력받은 총 개수 c가 주어집니다. (1 ≤ n ≤ 1000, 1 ≤ c ≤ 1000)
• 둘째 줄에는 n개의 메시지가 공백으로 구분되어 주어집니다.

출력 조건:

• 주어진 메시지를 빈도와 입력 순서를 기준으로 정렬하여 출력합니다.

---

문제 해결 코드

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

struct Message {
    string content; // 메시지 내용
    int count;      // 메시지 등장 횟수
    int order;      // 메시지 입력 순서
};

// 메시지 정렬 기준
bool cmp(const Message &a, const Message &b) {
    if (a.count == b.count) {
        return a.order < b.order; // 등장 횟수가 같다면 입력 순서로 정렬
    }
    return a.count > b.count; // 등장 횟수 내림차순
}

int main() {
    int n, c;
    cin >> n >> c;

    map<string, int> frequency; // 메시지 등장 횟수
    map<string, int> firstOrder; // 메시지 입력 순서
    vector messages; // 메시지 리스트

    string s;
    for (int i = 0; i < n; i++) {
        cin >> s;
        frequency[s]++;
        if (firstOrder.find(s) == firstOrder.end()) {
            firstOrder[s] = i; // 첫 번째 등장 순서 저장
        }
    }

    // 메시지 정보를 리스트에 저장
    for (const auto &entry : frequency) {
        messages.push_back({entry.first, entry.second, firstOrder[entry.first]});
    }

    // 정렬
    sort(messages.begin(), messages.end(), cmp);

    // 출력
    for (const auto &message : messages) {
        for (int i = 0; i < message.count; i++) {
            cout << message.content << ' ';
        }
    }

    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 메시지의 빈도와 입력 순서를 기준으로 정렬하여 메시지를 출력합니다.

• 입력 처리:
  • `frequency`: 각 메시지의 빈도를 저장합니다.
  • `firstOrder`: 각 메시지가 처음 입력된 순서를 저장합니다.
• 정렬:
  • `cmp` 함수는 메시지를 등장 횟수 내림차순으로 정렬합니다.
  • 등장 횟수가 같다면 입력 순서를 기준으로 정렬합니다.
• 출력:
  • 정렬된 메시지를 등장 횟수만큼 출력합니다.

시간 복잡도 분석:

• 입력 처리: O(n).
• 정렬: O(n log n).
• 출력: O(n).

따라서 전체 시간 복잡도는 O(n log n)입니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
8 5
a a a b b c c c b

출력:
a a a b b b c c c

메시지는 등장 횟수와 입력 순서를 기준으로 정렬되어 출력됩니다.

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