선밥의 공부하는 블로그

모의고사

문제 링크

모의고사

분석

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를 반복합니다.

answers를 가장 많이 맞춘 사람을 반환해야합니다.
가장 많이 맞춘 사람이 여러명일경우 오름차순으로 반환해야합니다.

풀이

#include <vector>

using namespace std;

vector<int> solution(vector<int> answers) {
    vector<int> answer;
    
    vector<int> one { 1, 2, 3, 4, 5 };
    vector<int> two { 2, 1, 2, 3, 2, 4, 2, 5 };
    vector<int> three { 3, 3, 1, 1, 2, 2, 4, 4, 5, 5 };
    
    int isOneCorrect = 0;
    int isTwoCorrect = 0;
    int isThreeCorrect = 0;
    
    for (int i = 0; i < answers.size(); ++i)
    {
        isOneCorrect += (answers[i] == one[i % one.size()]) ? 1 : 0;
        
        isTwoCorrect += (answers[i] == two[i % two.size()]) ? 1 : 0;
        
        isThreeCorrect += (answers[i] == three[i % three.size()]) ? 1 : 0;
    }
    
    int highestCorrect = (isOneCorrect > isTwoCorrect) ? isOneCorrect : isTwoCorrect;
    highestCorrect = (highestCorrect > isThreeCorrect) ? highestCorrect : isThreeCorrect;
        
    if (highestCorrect == isOneCorrect)
    {
        answer.push_back(1);
    }
    if (highestCorrect == isTwoCorrect)
    {
        answer.push_back(2);
    }
    if (highestCorrect == isThreeCorrect)
    {
        answer.push_back(3);
    }
    
    return answer;
}

one, two, three는 각 수포자가 문제를 찍는 규칙을 가집니다.

isOneCorrect, isTwoCorrect, isThreeCorrect는 각 수포자가 문제를 맞춘 개수를 저장합니다.

반복문에서 각 수포자들이 문제를 맞췄는지 확인하고 맞춘 개수를 증가합니다.

이후 코드에서 가장 많이 맞춘 개수를 찾고, 많이 맞춘 사람을 반환합니다.

리팩토링한 코드는 다음과 같습니다.

#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> answers) {
    vector<int> answer;
    
    vector<int> one { 1, 2, 3, 4, 5 };
    vector<int> two { 2, 1, 2, 3, 2, 4, 2, 5 };
    vector<int> three { 3, 3, 1, 1, 2, 2, 4, 4, 5, 5 };
    
    vector<int> Correct(3, 0);
    
    for (int i = 0; i < answers.size(); ++i)
    {
        if (answers[i] == one[i % one.size()]) ++Correct[0];
        
        if (answers[i] == two[i % two.size()]) ++Correct[1];
        
        if (answers[i] == three[i % three.size()]) ++Correct[2];
    }
    
    int highestCorrect = *(max_element(Correct.begin(), Correct.end()));
    
    for (int i = 0; i < Correct.size(); ++i)
    {
        if (highestCorrect == Correct[i])
        {
            answer.push_back(i + 1);
        }
    }
    
    return answer;
}

Correct는 배열을 사용해 각 수포자가 문제를 맞춘 개수를 저장합니다.

std::max_element를 사용해 가장 높은 값을 찾습니다.

그 다음 반복문에서 가장 높은 값과 같은 점수의 수포자를 반환하는 값으로 저장합니다.

성능 요약

리팩토링 전 성능은 다음과 같습니다.

시간 복잡도는 answers를 순회하므로 $O(n)$입니다.
공간 복잡도는 고정된 크기의 추가 메모리를 사용하므로 $O(1)$입니다.

테스트 1 〉 통과 (0.01ms, 3.67MB)
테스트 2 〉 통과 (0.01ms, 4.17MB)
테스트 3 〉 통과 (0.01ms, 3.59MB)
테스트 4 〉 통과 (0.01ms, 4.15MB)
테스트 5 〉 통과 (0.01ms, 4.15MB)
테스트 6 〉 통과 (0.01ms, 4.15MB)
테스트 7 〉 통과 (0.04ms, 4.21MB)
테스트 8 〉 통과 (0.01ms, 3.75MB)
테스트 9 〉 통과 (0.05ms, 4.17MB)
테스트 10 〉 통과 (0.03ms, 4.15MB)
테스트 11 〉 통과 (0.05ms, 4.21MB)
테스트 12 〉 통과 (0.05ms, 4.17MB)
테스트 13 〉 통과 (0.01ms, 4.21MB)
테스트 14 〉 통과 (0.05ms, 4.21MB)

리팩토링 한 성능은 다음과 같습니다.

시간 복잡도와 공간 복잡도는 리팩토링 전과 같습니다.

테스트 1 〉 통과 (0.01ms, 3.68MB)
테스트 2 〉 통과 (0.01ms, 4.2MB)
테스트 3 〉 통과 (0.02ms, 4.21MB)
테스트 4 〉 통과 (0.01ms, 4.14MB)
테스트 5 〉 통과 (0.01ms, 4.21MB)
테스트 6 〉 통과 (0.01ms, 4.21MB)
테스트 7 〉 통과 (0.06ms, 4.15MB)
테스트 8 〉 통과 (0.03ms, 4.21MB)
테스트 9 〉 통과 (0.10ms, 4.21MB)
테스트 10 〉 통과 (0.06ms, 3.88MB)
테스트 11 〉 통과 (0.10ms, 4.21MB)
테스트 12 〉 통과 (0.09ms, 3.99MB)
테스트 13 〉 통과 (0.01ms, 3.68MB)
테스트 14 〉 통과 (0.06ms, 3.88MB)

Programmers 카테고리 내 다른 글 보러가기

댓글남기기

최근 글