[C++] Programmers Lv. 1 "모의고사"

🔵 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42840

프로그래머스

 

🔵 문제 설명

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

 

❗ Key Point

• 반복되는 패턴 처리
• STL을 활용해서 손쉽게 최대값 찾기

 

💡알고리즘

1. 각 수포자의 답안 패턴을 이용해서 입력으로 들어오는 answers 배열과 비교 후, 점수를 수포자 배열에 저장한다. (% 연산으로 반복 패턴 비교)
2. 수포자 배열 중 최대 점수를 구한다. (STL의 max_element 사용)
3. 최대 점수가 여러 명일 수도 있으므로 모두 구하여 answer 배열에 push 하고 반환한다.

 

🔵 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> answers) 
{
    vector<int> score(3);   // 각 수포자가 얻은 점수
    vector<int> answer;
 
    // 수포자 답안 패턴
    vector<int> person1 = { 1, 2, 3, 4, 5};
    vector<int> person2 = { 2, 1, 2, 3, 2, 4, 2, 5 };
    vector<int> person3 = { 3, 3, 1, 1, 2, 2, 4, 4, 5, 5 };

    for (int i = 0; i < answers.size(); i++)
    {
        // 수포자 1
        if (answers[i] == person1[i % person1.size()])
            ++score[0];

        // 수포자 2
        if (answers[i] == person2[i % person2.size()])
            ++score[1];

        // 수포자 3
        if (answers[i] == person3[i % person3.size()])
            ++score[2];
    }

    // 최대값 찾기
    int maxScore = *max_element(score.begin(), score.end());

    // 최대값이 여러개일 경우를 가정하고 구현
    // 낮은 인덱스부터 비교하므로 따로 정렬할 필요 없음
    for (int i = 0; i < 3; i++)
    {
        if (maxScore == score[i])
            answer.push_back(i + 1);    // 수포자 인덱스는 1부터 시작
    }

    return answer;
}

 

🔵 시간 복잡도

N은 answers(입력)의 길이이다.

N 영향을 받는 부분은 for문인데, 이는 단순히 N만큼 순회하며 계산하므로 시간 복잡도는 O(N)이다.