[PCCP] Lv1: 모의고사(42840) 해설

문제

- 문제 링크: 모의고사

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 수포자별 패턴 정의

2) 수포자별 맞힌 문제 개수 기록

3) 가장 많은 문제를 맞힌 수포자 기록

 

코드

(C언어) 

 

(C++) 

solution 1)

- N: answers의 길이

- 각 수포자들 패턴과 정답 비교: O(N)

- scores 순회하며 가장 높은 점수 탐색하여 수포자 추가 연산: O(1)

- 최종 시간 복잡도: O(N)

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

using namespace std;

// 각 수포자 패턴 정의
vector<int> first = {1, 2, 3, 4, 5};
vector<int> second = {2, 1, 2, 3, 2, 4, 2, 5};
vector<int> third = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};

vector<int> solution(vector<int> answers) {
    vector<int> answer; // 가장 많이 문제를 맞힌 사람이 저장될 벡터
    vector<int> matchCnt(3); // 각 수포자별 맞힌 문제 개수를 저장할 벡터

    // 실제 정답과 각 수포자들의 패턴을 비교해서 맞힌 개수
    for (int i = 0; i < answer.size(); ++i) {
        if (answers[i] == first[i % first.size()])
            matchCnt[0]++;
        if (answers[i] == second[i % second.size()])
            matchCnt[1]++;
        if (answers[i] == third[i % third.size()])
            matchCnt[2]++;
    }
    
    // 가장 많이 맞힌 수포자가 얻은 점수
    int max_score = *max_element(matchCnt.begin(), matchCnt.end());
    
    // 가장 많이 맞힌 수포자의 번호를 저장
    for (int i = 0; i < 3; ++i) {
        if (matchCnt[i] == max_score)
            answer.push_back(i + 1);
    }

    return answer;
}

 

solution 2)

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

using namespace std;

vector<int> solution(vector<int> answers) {
    vector<int> answer;
    
    int stu1[5] = {1,2,3,4,5};
    int stu2[8] = {2,1,2,3,2,4,2,5};
    int stu3[10] = {3,3,1,1,2,2,4,4,5,5};
    
    int score[3] ={0, 0, 0};
    for (int i = 0; i < answers.size(); i++)
    {
        if (stu1[i % 5] == answers[i])
            score[0]++;
        if (stu2[i % 8] == answers[i])
            score[1]++;
        if (stu3[i % 10] == answers[i])
            score[2]++;
    }
    
    int max_score = *max_element(score, score+3);
    for (int i = 0; i < 3; i++)
    {
        if (score[i] == max_score)
            answer.push_back(i+1);
    }
    return answer;
}

solution 3)

#include <string>
#include <vector>

using namespace std;

std::vector<int> stu1 = {1,2,3,4,5};
std::vector<int> stu2 = {2,1,2,3,2,4,2,5};
std::vector<int> stu3 = {3,3,1,1,2,2,4,4,5,5};

vector<int> solution(vector<int> answers) {
    vector<int> answer;
    int score1 = 0; 
    int score2 = 0;
    int score3 = 0;
        
    for (size_t i = 0; i < answers.size(); ++i) {
        if (stu1[i%stu1.size()] == answers[i]) score1++;
        if (stu2[i%stu2.size()] == answers[i]) score2++;
        if (stu3[i%stu3.size()] == answers[i]) score3++;
    }

    int max_val = 0;
    
    if (score1 > max_val)
        max_val = score1;
    if (score2 > max_val)
        max_val = score2;
    if (score3 > max_val)
        max_val = score3;
    
    if (max_val == score1)
        answer.push_back(1);
    if (max_val == score2)
        answer.push_back(2);
    if (max_val == score3)
        answer.push_back(3);
    
    return answer;
}

 

(C#) 

 

(Java) 

solution1) 

- N: answers의 길이

- 각 수포자들의 패턴과 정답을 비교하는 부분: O(N)

- 이후 scores를 순회하면서 가장 높은 점수를 받은 수포자를 추가하는 연산: O(N)

- 최종 시간 복잡도: O(N)

import java.util.ArrayList;
import java.util.Arrays;


class Solution {
    public int[] solution(int[] answers) {
        // 수포자들의 패턴
        int[][] pattern = {
            {1, 2, 3, 4, 5},
            {2, 1, 2, 3, 2, 4, 2, 5},
            {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}
        };
        
        // 수포자들의 점수를 저장할 배열
        int[] scores = new int[3];
        
        // 각 수포자의 패턴과 정답이 얼마나 일치하는지 확인
        for (int i = 0; i < answers.length; ++i) {
            for (int j = 0; j < pattern.length; ++j) {
                if (answers[i] == pattern[j][i % pattern[j].length]) {
                    scores[j]++;
                }
            }
        }
        
        // 가장 높은 점수 저장
        int maxScore = Arrays.stream(scores).max().getAsInt();
        // 가장 높은 점수를 가진 수포자들의 번호를 찾아서 리스트에 담음
        ArrayList<Integer> answer = new ArrayList();
        for (int i = 0; i < scores.length; ++i) {
            if (scores[i] == maxScore) {
                answer.add(i + 1);
            }
        }
        
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

solution2) 

 

solution3) 

 

 

(Python) 

solution1)

- N: answers의 길이

- 각 수포자들의 패턴과 정답을 비교하는 부분: O(N)

- scores를 순회하면서 가장 높은 점수를 받은 수포자를 추가하는 연산: O(1)

- 최종시간복잡도: O(N)

def solution(answers):
    # 수포자들의 패턴
    patterns = [
        [1, 2, 3, 4, 5],
        [2, 1, 2, 3, 2, 4, 2, 5],
        [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
    ]
    
    # 수포자들의 점수를 저장할 리스트
    scores = [0] * 3
    
    # 각 수포자의 패턴과 정답이 얼마나 일치하는지 확인
    for i, answer in enumerate(answers):
        for j, pattern in enumerate(patterns):
            if answer == pattern[i % len(pattern)]:
                scores[j] += 1
        # 가장 높은 점수 저장
        max_score = max(scores)
        # 가장 높은 점수를 가진 수포자들의 번호를 찾아서 리스트에 담음
        highest_scores = [ ]
        for i, score in enumerate(scores):
            if score == max_score:
                highest_scores.append(i + 1)
    return highest_scores

solution2)

def solution(answers):
    answer = []
    students = [
        [1, 2, 3, 4, 5],
        [2, 1, 2, 3, 2, 4, 2, 5],
        [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
    ]
    scores = [0 for _ in range(3)]
    
    for i in range(len(answers)):
        if answers[i] == students[0][i%5]:
            scores[0] += 1
        if answers[i] == students[1][i%8]:
            scores[1] += 1
        if answers[i] == students[2][i%10]:
            scores[2] += 1
    max_score = max(scores)
    for i, score in enumerate(scores):
        if score == max_score:
            answer.append(i+1)
    return answer

 

 

solution3) 

 

 

(JavaScript) 

solution1) 

- N: answers의 길이

- 각 수포자들의 패턴과 정답을 비교하는 부분: O(N)

- scores를 순회하면서 가장 높은 점수를 받은 수포자를 추가하는 연산: O(1)

- 최종시간복잡도: O(N)

function solution(answers) {
    // 수포자들의 패턴
    const patterns = [
        [1, 2, 3, 4, 5], // 1번 수포자의 찍기 패턴
        [2, 1, 2, 3, 2, 4, 2, 5], // 2번 수포자의 찍기 패턴
        [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] // 3번 수포자의 찍기 패턴
    ];
    
    // 수포자들의 점수를 저장할 배열
    const scores = [0, 0 ,0];
    
    // 각 수포자의 패턴과 정답이 얼마나 일치하는지 확인
    for (const [i, answer] of answers.entries()) {
        for (const [j, pattern] of patterns.entries()) {
            if (answer === pattern[i % pattern.length]) {
                scores[j] += 1;
            }
        }
    }
    
    // 가장 높은 점수 저장
    const maxScore = Math.max(...scores);
    
    // 가장 높은 점수를 받은 수포자들의 번호를 찾아서 배열에 담음
    const highestScores = [];
    for (let i = 0; i < scores.length; ++i) {
        if (scores[i] === maxScore) {
            highestScores.push(i + 1);
        }
    }
    
    return highestScores;
}

solution2)

d

 

solution3)  

d