[백준] 대표 선수

서론

오늘의 코딩 테스트 문제는 백준 2461번 "대표 선수"다. 각 학급에서 한 명씩 선발해 능력치 차이를 최소화하는 문제다. 투 포인터 연습용으로 골랐다.

문제 분석

문제 요약:

•

N개 학급, 각 학급 M명의 학생

•

각 학생은 고유한 능력치를 가짐

•

각 학급에서 1명씩 선발

•

선발된 학생들의 능력치 최대값과 최소값의 차이를 최소화

핵심 포인트:

•

N명 선발 시 능력치 최대-최소 차이의 최소값을 찾아야 함

•

1 ≤ N, M ≤ 1,000이므로 O(N*M) 이하의 복잡도 필요

계획 수립

접근 방식:

각 학급 능력치 내림차순 정렬

우선순위 큐로 각 학급의 최대값 관리

최소값 갱신하며 차이 계산

알고리즘: 우선순위 큐 + 그리디

데이터 구조:

•

2차원 vector: 각 학급 학생들의 능력치 저장

•

priority_queue: 현재 선택된 학생들 중 최대값 관리

코드 작성

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int main ()
{
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> classes;

    for (int i = 0; i < n; i++)
    {
        vector<int> temp;
        for (int j = 0; j < m; j++)
        {
            int a;
            cin >> a;
            temp.push_back(a);
        }
        sort(temp.rbegin(), temp.rend());
        classes.push_back(temp);
    }

    int min_value = 1000000000;

    priority_queue<pair<int, pair<int, int>>> pq;
    for (int i = 0; i < n; i++)
    {
        pq.push({classes[i][0], {i, 0}});
        if (min_value > classes[i][0])
            min_value = classes[i][0];
    }

    int answer = 1000000000;
    while (true)
    {
        pair<int, pair<int, int>> max = pq.top();
        pq.pop();

        if (answer > max.first - min_value)
            answer = max.first - min_value;

        if (max.second.second == m-1)
            break;
        if (min_value > classes[max.second.first][max.second.second+1])
            min_value = classes[max.second.first][max.second.second+1];
        
        pq.push({classes[max.second.first][max.second.second+1], {max.second.first, max.second.second+1}});
    }

    cout << answer << endl;

    return 0;
}
C++
복사

주요 로직:

각 학급 능력치 내림차순 정렬

우선순위 큐에 각 학급 최고 능력치 학생 넣기

최소값 갱신

루프:

•

최대값(큐 top) 꺼내기

•

현재 차이 계산 및 정답 갱신

•

다음 학생 큐에 넣기

•

최소값 갱신

답 출력

문제 해결 및 보완

처음엔 단순 투 포인터로 접근했다가 실패. 반례를 찾아보니 문제점 발견.

반례:

Plain Text
복사

예상 출력: 5

초기 로직 출력: 6

원인: 한 학급 기준으로 가까운 학생 선택 시 최적값 놓침

해결: 우선순위 큐 활용해 매 단계 최적의 선택

회고

엣지 케이스에 대한 고민이 부족했다. 문제 풀고 나서 한참 헤매는 일이 잦아지고 있어 주의가 필요하다.

개선점:

문제 풀이 전 다양한 케이스 고려하는 습관 들이기

반례 찾는 능력 키우기