SWEA 1204. 최빈수 구하기

• 문제 링크 : 1204. 최빈수 구하기

문제 요약

학생 1000명의 점수(0점 이상 100점 이하)가 주어질 때 최빈수, 즉 가장 많이 나온 점수를 구한다. 가장 많이 나온 점수가 여럿이면 그중 가장 큰 점수를 답한다. 각 테스트 케이스는 번호 한 줄과 점수 1000개로 주어지고, 출력은 #번호 최빈수 형식이다.

---

1. 문제 해석

이 문제는 배열의 인덱스에 해당하는 값을 카운트하는 방식에 대해 학습할 수 있는 문제이다.

score[100]배열을 만들고, 각 점수에 해당하는 부분을 score[해당 학생의 점수]++ 해주면 결과적으로 모든 학생들의 점수에 대한 카운트가 저장될 것이다.

그러면 0점부터 100점 까지 카운트 값이 크거나 같은 것에 해당하는 점수(인덱스)를 정답으로 출력하면 된다. 이때 카운트 값을 출력하는 것이 아닌 인덱스 값을 출력해야 한다는 점에 주의해야 한다. 인덱스 값이 점수에 해당하기 때문이다.

---

2. 문제 풀이

student배열 사용

#include <iostream>
using namespace std;
int student[1000];

int solution(int score[100]){
    int answer=0, max_score=0;
    for(int i=0;i<100;++i){
        if(max_score<=score[i]) {
            max_score=score[i];
            answer=i;
        }
    }
    return answer;
}

int main(int argc, char** argv) {
    int test_case;
    int T;
    cin >> T;
    for(test_case = 1; test_case <= T; ++test_case) {
        int tn; cin >> tn;
        int score[100]={0,};
        for(int i=0;i<1000;++i){
            cin >> student[i];
            score[student[i]]+=1;
        }
        cout << "#" << test_case << " " << solution(score) << "\n";
    }
    return 0;
}

student배열 사용 x

#include <iostream>
using namespace std;
#define STUD_NUM 1000

int solve(){
    int answer = 0, score, scores[100] = {0};
    for(int i=0; i<STUD_NUM; ++i){
        cin >> score;
        scores[score]++;
    }
    int max_score = 0;
    for(int i=0; i<100; ++i){
        if(max_score <= scores[i]){
            max_score = scores[i];
            answer = i;
        }
    }
    return answer;
}
int main(int argc, char** argv) {
    int test_case, T;
    freopen("1204_input.txt", "r", stdin);
    cin >> T;
    for(test_case = 1; test_case <= T; ++test_case) {
        int test_num;
        cin >> test_num;
        cout << "#" << test_case << " " << solve() << endl;
    }
    return 0;
}

---

동점일 때 가장 큰 점수를 고르는 방법

두 풀이 모두 비교에 <=를 쓴다. 점수를 0부터 위로 올라가며 보기 때문에, 카운트가 같으면 나중에 본 점수, 즉 더 큰 점수가 answer를 덮어쓴다. “최빈수가 여러 개일 때에는 가장 큰 점수를 출력하라”는 조건을 이 등호 하나로 처리한 것이다. <로 바꾸면 동점일 때 가장 작은 점수가 남아 오답이 된다.

---

배열 크기에서 놓친 부분

두 풀이에는 공통된 문제가 있다. 제약 사항에 따르면 점수는 0점 이상 100점 이하이므로 가능한 점수는 0부터 100까지 101개다. 그런데 카운트 배열은 score[100], scores[100]으로 크기가 100이고, 최빈수를 찾는 반복도 i<100까지만 돈다.

• 100점을 받은 학생이 있으면 score[100]에 접근한다. 크기 100인 배열의 마지막 인덱스는 99이므로 범위를 벗어난 쓰기이고, C++에서는 정의되지 않은 동작이다.
• 100점이 최빈수인 입력이라면, 반복이 99에서 끝나므로 100을 답으로 고를 수 없다.

테스트 데이터에 100점이 최빈수로 나오지 않았다면 통과했을 수 있지만, 조건상으로는 틀린 코드다. 위 코드는 기록으로 그대로 두고, 고친 버전을 따로 적는다. 바뀐 곳은 배열 크기와 반복 범위 두 군데다.

#include <iostream>
using namespace std;

const int STUD_NUM = 1000;
const int MAX_SCORE = 100;

int solve() {
    int counts[MAX_SCORE + 1] = {0};       // 0점부터 100점까지 101칸
    for (int i = 0; i < STUD_NUM; ++i) {
        int score;
        cin >> score;
        counts[score]++;
    }
    int answer = 0, maxCount = 0;
    for (int s = 0; s <= MAX_SCORE; ++s) { // 100점까지 포함
        if (maxCount <= counts[s]) {       // 동점이면 더 큰 점수로 갱신
            maxCount = counts[s];
            answer = s;
        }
    }
    return answer;
}

int main() {
    int T;
    cin >> T;
    for (int test_case = 1; test_case <= T; ++test_case) {
        int test_num;
        cin >> test_num;
        cout << "#" << test_case << " " << solve() << '\n';
    }
    return 0;
}

두 번째 원래 풀이에 있는 freopen("1204_input.txt", "r", stdin);은 로컬에서 입력 파일로 테스트할 때 쓰는 줄이다. 제출할 때는 표준 입력으로 데이터가 들어오므로 지우거나 주석으로 막아야 한다. 고친 버전에서는 빼 두었다.

---

복잡도

• 시간: 테스트 케이스마다 O(학생 수 + 점수 범위) = O(1000 + 101).
• 공간: O(점수 범위). 학생 점수를 저장할 필요 없이 카운트 배열만 있으면 된다. 첫 번째 풀이의 student 배열이 없어도 되는 이유다.

이처럼 값의 범위가 작고 정해져 있을 때 값을 인덱스로 쓰는 카운팅 배열은 정렬이나 맵 없이 빈도를 셀 수 있는 가장 단순한 방법이다.