프로그래머스 완전탐색 모의고사

금방 할 줄 알았는데... c++이 아직도 너무 어색해서 오래걸렸다.

맨날 온라인 컴파일러로만 하다가 ide 세팅을 오늘 했다! (참고: velog.io/@cookncoding/VS-Code%EC%97%90-C-%EA%B0%9C%EB%B0%9C-%ED%99%98%EA%B2%BD-%EC%84%B8%ED%8C%85%ED%95%98%EA%B8%B0)

 

일단 문제

문제 설명 링크

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

입출력 예

answersreturn

[1,2,3,4,5]	[1]
[1,3,2,4,2]	[1,2,3]

입출력 예 설명

입출력 예 #1

• 수포자 1은 모든 문제를 맞혔습니다.
• 수포자 2는 모든 문제를 틀렸습니다.
• 수포자 3은 모든 문제를 틀렸습니다.

따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.

입출력 예 #2

• 모든 사람이 2문제씩을 맞췄습니다.

 

일단 문제를 보고 처음 든 생각은 세 사람 각각에 대한 함수를 만들어서 맞은 갯수를 리턴하는 함수를 만들자! 였다.

int scoring1(vector<int> answers)
{
    array<int, 5> pattern = {1, 2, 3, 4, 5};
    int score = 0;
    int *first = &answers[0];
    for (int i = 0; i < answers.size(); ++i)
        if (pattern[i % 5] == *(first + i))
            ++score;
    return score;
}

int scoring2(vector<int> answers)
{
    array<int, 8> pattern = {2, 1, 2, 3, 2, 4, 2, 5};
    int score = 0;
    int *first = &answers[0];
    for (int i = 0; i < answers.size(); ++i)
        if (pattern[i % 8] == *(first + i))
            ++score;
    return score;
}

int scoring3(vector<int> answers)
{
    array<int, 10> pattern = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};

    int score = 0;
    int *first = &answers[0];
    for (int i = 0; i < answers.size(); ++i)
        if (pattern[i % 10] == *(first + i))
            ++score;
    return score;
}

예상대로 잘 동작한다.

순회할 때 포인터 방식을 쓴 이유는 저게 빠르기도 하고, pattern 값을 사용할 때 인덱스가 필요해서이다.

 

시간을 재고 풀었는데, 여기까지는 쉬워서 10분 남짓 걸린 것 같다. 그런데 의외로 애를 먹였던 것은 바로 이 조건이었다.

• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

첨엔 사람이 세 명 밖에 안되니까 굳이 반복문으로 해야하나 생각이 들었는데, 생각을 하면 할 수록 로직 짜는게 좀 짜증났다.

사람이 많으면 map써서 정렬하고 같은 점수일 때 까지 뽑으면 될 텐데, 세 명인데 그렇게 하기는 뭔가.. 로직 짜는 시간이 아깝다는... 생각이 들었다. (나중에 생각하기로는 차라리 이 때 빨리 끝내는게 나았다.)

최대한 다른 배열 안쓰고 하려했는데 안되고 결국은 이렇게 했다.

int max(int a, int b ) {
    return a > b ? a : b;
}

vector<int> solution(vector<int> answers)
{
    vector<int> answer;
    array<int, 3> scores;
    
    scores[0] = scoring1(answers);
    scores[1] = scoring2(answers);
    scores[2] = scoring3(answers);
    
    int maxScore = max(max(scores[0], scores[1]), scores[2]);
    for (int i=0 ; i< 3; i++) 
        if (scores[i] == maxScore)
            answer.push_back(i +1);

    return answer;
}

 

scores 배열에 결괏값을 저장하고, max를 찾아서 같으면 answer에 넣는다. 

제출했더니 정답이다.

 

반복되는 코드가 많아서 정리를 좀 했다.

int max(int a, int b)
{
    return a > b ? a : b;
}

vector<int> solution(vector<int> answers)
{
    vector<int> answer;
    array<int, 3> scores = {
        0,
    };

    array<int, 5> pattern1 = {1, 2, 3, 4, 5};
    array<int, 8> pattern2 = {2, 1, 2, 3, 2, 4, 2, 5};
    array<int, 10> pattern3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};

    int *first = &answers[0];
    for (int i = 0; i < answers.size(); i++)
    {
        if (pattern1[i % 5] == *(first + i))
            scores[0]++;
        if (pattern2[i % 8] == *(first + i))
            scores[1]++;
        if (pattern3[i % 10] == *(first + i))
            scores[2]++;
    }

    int maxScore = max(max(scores[0], scores[1]), scores[2]);
    for (int i = 0; i < 3; i++)
        if (scores[i] == maxScore)
            answer.push_back(i + 1);

    return answer;
}

이게 최종 코드이다.

 

결과이다. 완전탐색이라 그런지 효율성 테스트는 없나보다... 의미가 없으니까?

 

 

개선 아이디어

딱히 없다. 어차피 완전 탐색이라 시간 복잡도를 줄이기는 힘들 것 같고, 공간 복잡도는 좀 줄일 수 있을 것 같긴 하다. 유의미할 것 같지는 않다.

 

 

다른 사람 코드 분석

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

using namespace std;

vector<int> one = {1,2,3,4,5};
vector<int> two = {2,1,2,3,2,4,2,5};
vector<int> thr = {3,3,1,1,2,2,4,4,5,5};

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

제일 먼저 나오는 코드(아마 제일 점수가 높은 코드일까?)

나랑 비슷한데, max 함수를 따로 안만들고 max_element라는 함수를 썼다. 외워둬야 겠다.

또 다른 점은 난 포인터를 썼고 이 사람은 그냥 배열 접근을 썼다는 것.