백준 5766번 [할아버지는 유명해!](C++) -yes6686- 티스토리

백준 문제 풀이: 5766 (할아버지는 유명해!)

---

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

문제 설명:

n명의 학생이 m개의 경기에 참가하여, 각 경기마다 1명의 학생이 승리한다. 경기 결과가 주어질 때, 전체 승리 횟수가 두 번째로 많은 학생(들)의 번호를 오름차순으로 출력하는 문제이다.

즉, 각 번호가 몇 번 승리했는지를 카운팅한 뒤, 승수 기준으로 정렬하여 두 번째로 높은 승수를 가진 사람을 출력하면 된다.

---

문제 해결 코드

// 5766번: 할아버지는 유명해!
// 승수 기준으로 정렬 후, 두 번째로 높은 승수를 가진 학생들 출력

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

pair<int, int> arr[10001];  // {승수, 학생 번호}

// 승수 기준 내림차순 정렬
bool compare1(pair<int, int> a, pair<int, int> b) {
    return a.first > b.first;
}

// 학생 번호 기준 오름차순 정렬
bool compare2(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}

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

    while (true) {
        int n, m;
        cin >> n >> m;
        if (n == 0 && m == 0) break;

        // 입력 처리 및 승수 누적
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int x;
                cin >> x;
                arr[x].first++;      // 승수 증가
                arr[x].second = x;   // 학생 번호 저장
            }
        }

        // 승수 기준 정렬하여 두 번째 승수 파악
        sort(arr, arr + 10000, compare1);
        int secondV = arr[1].first;  // 두 번째로 높은 승수

        // 다시 번호 기준 정렬하여 오름차순 출력
        sort(arr, arr + 10000, compare2);

        for (int i = 1; i < 10001; i++) {
            if (arr[i].second == 0) continue;           // 등장하지 않은 번호는 생략
            if (arr[i].first == secondV)                // 두 번째 승수인 경우 출력
                cout << arr[i].second << ' ';
        }
        cout << '\n';

        // 배열 초기화
        memset(arr, 0, sizeof(arr));
    }
}

---

코드 설명

• 핵심 알고리즘: 정렬 및 조건 필터링. 승수 기준 정렬 후, second highest 값 추출 → 다시 번호 기준 정렬 후 출력
• 구현 세부사항:
  • arr[x].first++: 해당 번호의 승수 증가
  • arr[x].second = x: 해당 번호 저장 (출력을 위한 정보)
  • sort(..., compare1): 승수 기준 정렬
  • sort(..., compare2): 번호 기준 정렬하여 출력 순서를 보장
  • memset으로 배열 초기화
• 시간 복잡도 분석:각 테스트케이스마다 O(n ⋅ m + 2 ⋅ N log N), 여기서 N ≤ 10000

---

결과

두 번째로 많은 승수를 가진 학생 번호들을 공백으로 구분하여 출력합니다.

예시 입력:
4 5
20 33 25 32 99
32 86 99 25 10
20 99 10 33 86
19 33 74 99 32
3 6
2 34 67 36 79 93
100 38 21 76 91 85
32 23 85 31 88 1
0 0

예시 출력:
32 33
1 2 21 23 31 32 34 36 38 67 76 79 88 91 93 100

다른 접근 방식이나 개선 아이디어가 있다면 댓글로 공유해주세요!