[Algorithm] 모의고사

문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 

수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 

• 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 
• 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 
• 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

문제 유형

• 완전 탐색

 

문제 풀이 방

1. 모든 학생들의 채점 결과를 계산한다.
2. 채점 결과를 내림차순으로 정렬한다.
3. 첫번째 학생은 가장 높은 점수를 받았으며 반복문을 돌며 점수가 동일한 학생들을 결과에 추가한다.

 

코드 작성

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

struct student
{
    int idx;
    int score;
    vector<int> pattern;
};

bool compare(const student& a, const student& b)
{
    if (a.score > b.score)
        return true;
    return false;
}

vector<int> solution(vector<int> answers) {  
    vector<student> students =
    {
        {1, 0, {1, 2, 3, 4, 5}},
        {2, 0, {2, 1, 2, 3, 2, 4, 2, 5}},
        {3, 0, {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}}
    };
    
    vector<int> result;
    
    // 더한다.
    for (int j = 0; j < students.size(); j++)
    {
        int size = students[j].pattern.size();
        for (int i = 0; i < answers.size(); i++)
        {
            if (answers[i] == students[j].pattern[i % size])
                students[j].score += 1;
        }  
    }
    
    // 내림차순 정렬한다.
    sort(students.begin(), students.end(), compare);
    
    // 소거한다.
    int maxScore = students[0].score;
    result.push_back(students[0].idx);
    for (int i = 1; i < students.size(); i++)
    {
        if (students[i].score < maxScore)
        {
            break;
        }
        
        result.push_back(students[i].idx);
    }
    
    return result;
}