모의고사

프로그래머스 - 모의고사

문제

---

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 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 함수를 작성해주세요.

제한사항

---

• 시험은 최대 10,000 문제로 구성
• 정답은 1, 2, 3, 4, 5 중 하나
• 가장 높은 점수를 받은 사람이 여럿일 경우 오름차순으로 정렬 후 return

💡Idea

1. 각 학생별 답안을 어떻게 저장할까?
   - 배열을 만들어서 저장하자.
   → 1번 수포자 : [1, 2, 3, 4, 5]
   → 2번 수포자 : [2, 1, 2, 3, 2, 4, 2, 5]
   → 3번 수포자 : [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
2. 답을 어떻게 비교할까?
   ① 각 학생들의 답을 포인터 변수를 선언하여 인덱스를 벗어나면 다시 0으로 초기화하면서 비교하자.
   → 인덱스를 계속해서 증가시키고 초기화하는 게 번거로움.
   ② 각 인덱스로 바로 접근할 수 있는 방법이 없을까?
   → 1번 수포자의 인덱스는 0 ~ 4, 2번 수포자는 0 ~ 7, 3번 수포자는 0 ~ 9이다.
   → 이 점을 이용하여 i를 각각의 답안 크기만큼 나눈 나머지를 인덱스로 사용하자 !!!
3. 제일 많이 맞춘 학생을 어떻게 구할까?
   ① 각 학생의 점수를 계산하는 배열을 만들자.
   → 이때 학생들의 점수를 다 비교해봐야하는 문제 발생,,
   ② 점수를 계산하면서 동시에 제일 높은 점수를 저장하자.
   

SourceCode

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> answers) {
    vector<int> answer;
    int student1[5] = {1, 2, 3, 4, 5}; // 1번 수포자
    int student2[8] = {2, 1, 2, 3, 2, 4, 2, 5}; // 2번 수포자
    int student3[10] = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}; // 3번 수포자
    int score[3] = {0}, cutline = 0; // 학생별 점수
   
    for(int i=0; i<answers.size(); i++) {
        if(answers[i] == student1[i % 5]) {
            score[0]++;
            cutline = max(score[0], cutline);
        }
        if(answers[i] == student2[i % 8]) {
            score[1]++;
            cutline = max(score[1], cutline);
        }
        if(answers[i] == student3[i % 10]) {
            score[2]++;
            cutline = max(score[2], cutline);
        }
    }
   
    for(int i=0; i<3; i++) {
        if(cutline == score[i]) {
            answer.push_back(i+1);
        }
    }
   
    return answer;
}

Feedback

---

1. 처음에 문제 풀 때 최악의 상황을 고려하여 시간 복잡도를 계산해보았다.
   - 최악의 상황에서 문제는 10000개, 학생은 3명이다.
   - 만약 10000개를 하나씩 꺼내서 세 명의 학생을 본다고 해도 10000 * 3 즉, O(30000)이다.
   → 시간 복잡도를 고려하는 것이 습관화되지 않아서 뿌듯했다.
2. max값을 구하는 게 항상 고민이었는데 다른 사람들의 풀이를 보니 max_element함수를 알게되었다.

Remind

---

• max_element(시작 주소, 끝 주소)로 사용한다.
• 주의할 점은 이 함수는 값이 아니라 주소를 return 한다.
• 값을 참조하기 위해서는 *연산자를 붙여서 *max_element(arr, arr+size)이런식으로 써야한다 !