[C++] 프로그래머스 모의고사

programmers.co.kr/learn/courses/30/lessons/42840

 

 

코딩테스트 연습 - 모의고사

 

1. 서론

 

level 1 문제이다. 완전 탐색으로 푸는 문제란다. 근데 완전 탐색이 아직 어떤 유형인지 잘 모른다. 완전 탐색이니까 노가다인가?

 

2. 문제 풀이

 

한 시험이 있다. 학생은 세 명이고, 세 명 다 일정한 패턴으로 답을 찍기로 했다. 

 

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 

 

시험은 최대 10000 문제까지 나올 수 있다. 즉, 1문제가 나와도 10000문제가 나와도 세 학생은 위와 같은 패턴으로 답을 적어서 낸다.

그리고 이 문제의 답이 주어진다. 답이 주어지면 채점 후에 가장 많이 맞은 사람이 누구인지 출력한다.

 

입출력으로 예를 들면 1 3 2 4 2 가 정답이면 학생 1은 답이 1, 4로 두 개. 학생 2는 2, 2로 답이 두 개. 학생 3은 3, 2로 답이 두 개. 

즉, 학생 1, 2, 3이 모두 맞춘 수가 같으므로 1, 2, 3이 답으로 출력된다.

 

1) 나의 풀이

 

나는 이렇게 생각했다. 입력으로 일정 배열이 주어진다. 예를 들어 1 3 2 4 2가 주어졌으면, 학생 1, 2, 3의 답지를 그에 맞게 만든다.

즉, 5문제가 출제되었다 치고 학생 3명이 답안지를 만드는 것이다. 학생들은 각자 5개의 답을 패턴에 맞게 적는 것이다.

 

답: 1 3 2 4 2

 

학생 1: 1 2 3 4 5

학생 2: 2 1 2 3 2

학생 3: 3 3 1 1 2 

 

이런 식으로 놓고 답의 배열과 학생 1, 2, 3의 배열을 비교해서 채점을 한다. 그 후에 가장 많이 맞은 학생을 골라서 출력하는 형태이다. 

나는 정말로 모의고사를 볼 때를 생각했다. 문제에 맞춰서 답의 개수를 조절하는 방식. 각 학생의 패턴에 맞게, 또 그 문제 수에 맞게 배열을 생성하는 게 좀 번거로웠다. 패턴 자체는 이미 나와있는 것이라 단순하지만, 문제 수에 맞게 그 배열을 만들다 보니까 패턴을 공식화하는 게 어려웠다. 근데 그냥 지금 생각해보면 저 패턴대로 배열을 세 개 만들어서 개수를 원하는 만큼 넣어주면 쉬웠을 텐데 정말 바보다... 

너무 현실에 맞춰서 생각하는 것 같다. 문제를 문제로만 보면 풀이 방법이 완전 달라지는데.

 

2) 다른 사람들의 아이디어

 

다른 사람들은 어떻게 풀었나 봤다. 나처럼 푼 사람은 본 적이 없다.

다들 그냥 저 패턴을 그대로 배열화 한 후 그 수에 맞춰 채점하는 방식을 썼다. 

즉, 따로 문제 수에 맞춰 배열을 만들지 않고 그냥 저 배열을 그대로 끌고 와서 문제 수에 맞춰 반복하며 답 배열과 비교하는 방식을 쓴다.

정말 간단하고 내 코드보다 쉽다. 물론 구현하는 것 자체는 내가 생각한 방법보다 살짝 까다로울 수는 있다. 세 패턴의 길이가 다르니까 그에 맞춰서 반복하는 방법이 좀 어려울 것 같다.

 

3. 코드 설명

 

#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> answers) {
    vector<int> answer;
    vector<int> s1, s2, s3;
    vector<int> t;
    vector<int> max;
    int i, tmp = 0, m, s;
    int c1, c2, c3;

    //짝, 홀수일 경우 문제 길이 조절
    if (answers.size() % 2 != 0)
        s = answers.size() / 2 + 1;
    else
        s = answers.size() / 2;
    
    //학생 1
    for (i = 1; i <= answers.size(); i++)
    {
        tmp = i;
        if (i > 5)
            tmp %= 5;
        if (tmp == 0) tmp = 5;
        s1.push_back(tmp);
    }
     
    //학생 2 
    for (i = 1; i <= s; i++)
    {
        s2.push_back(2);

        tmp = i % 4;
        if (tmp == 0) tmp = 4;
        if (tmp >= 2) tmp++;
        s2.push_back(tmp);

        if(i == s && answers.size() % 2 != 0)
            s2.pop_back();
    }
    
    //학생 3
    t.push_back(3);
    t.push_back(1);
    t.push_back(2);
    t.push_back(4);
    t.push_back(5);
    
    for (i = 0; i < s; i++)
    {
        tmp = i;
        if (i >= 5)
            tmp %= 5;
        s3.push_back(t[tmp]);
        s3.push_back(t[tmp]);

        if (answers.size() % 2 != 0 && i == s - 1)
            s3.pop_back();      
    }

    // 학생 3명의 답 수 체크
    c1 = 0, c2 = 0, c3 = 0;
    for (i = 0; i < answers.size(); i++)
    {
        if (answers[i] == s1[i])
            c1++;
        if (answers[i] == s2[i])
            c2++;
        if (answers[i] == s3[i])
            c3++;
    }
    
    // 가장 많이 맞춘 사람 찾기
    max.push_back(c1);
    max.push_back(c2);
    max.push_back(c3);
    
    m = *max_element(max.begin(), max.end());
    
    if (m != 0)
    {
        if(c1 == m)
            answer.push_back(1);
    
        if(c2 == m)
            answer.push_back(2);
    
        if(c3 == m)
            answer.push_back(3); 
    }
    
    return answer;
}

 

answers는 답의 배열이다. answer는 많이 맞은 사람의 배열이다.

s1, s2, s3는 각각 학생 1, 2, 3의 답이 적혀있는 배열이다. 각 학생의 패턴에 맞혀서 문제의 수대로 넣어도 됐을 텐데 그 방법을 생각지도 못해서 패턴에 맞추기 위해 for문을 1부터 돌리면서 숫자를 쪼개고, 나누고 별 난리를 다쳤다. (절대 이렇게는 풀지 말자) 어쨌든 숫자 공중분해쇼 끝에 학생의 답을 패턴을 맞춰 넣었다. 

그 후 answers 배열과 학생들의 답 배열과 비교하며 답의 수를 체크한다.

체크한 답의 수는 max 배열에 넣고 가장 큰 값을 가진 학생을 answer 배열에 넣는다.

세 명이 다 같은 수면 다 들어가고 아니면 최고인 학생이. (여럿일 수도 있고 한 명일 수도 있다.)

 

간단한 문제를 이렇게 어렵게도 풀 수 있다니... 진짜 놀랍다, 나 자신이. 코드 길이도 어마어마하고 선언된 변수들도 어마어마하다. 

문제 풀 때 팁... 현실적으로 문제를 해결하려고 하지 말 것. 문제를 문제로 바라볼 것. 정렬, 비교, 패턴화 등등....