[프로그래머스 코딩테스트 고득점 Kit - 완전탐색] 모의고사

완전탐색 문제

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

 

 

---

[문제 설명]

 

특수한 패턴으로 찍는 세 사람들 중 답을 누가 가장 많이 맞힐 수 있는지에 대한 문제입니다.

설명이 필요할 만큼 어려운 문제는 아닙니다.

 

각 사람들이 갖고 있는 패턴과 정답을 비교해 나가면서 누가 가장 많이 맞췄는가를 세주면 문제는 해결됩니다.

 

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]의 패턴을 가지고 있습니다.

 

 

여기서 어려울 수 있는 딱 하나의 문제가 있는데, answer의 길이에 따라 패턴을 형성하려면 꽤 복잡합니다.

1번 수포자를 예시로 들면 [1, 2, 3, 4, 5]라는 배열을 만들고,

그 뒤에 answer의 길이에 따라 [1, 2, 3, 4, 5]를 덧붙여 주는 식으로 풀이가 가능하지만 복잡합니다.

 

이런 문제를 피하기 위해 나머지 연산을 사용합니다.

1번 수포자를 예시로 들면 [1, 2, 3, 4, 5]의 패턴을 갖고 있으므로 6번째 문제의 답부터는 (6 % 5)의 값인 1번째 패턴의 값 1과 비교하면 됩니다.

 

위처럼 문제를 풀이한다면 시험 문제 n개에 대해 $O(n)$의 시간 복잡도로 이 문제를 해결할 수 있습니다.

 

---

[소스 코드] / C++

 

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

using namespace std;

vector<int> solution(vector<int> answers) {
    int f = 0, s = 0, t = 0;
    
    vector<int> fpt = {1, 2, 3, 4, 5}, spt = {2, 1, 2, 3, 2, 4, 2, 5}, tpt = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
    
    for (int i = 0; i < answers.size(); i++) {
        if (answers[i] == fpt[i % 5]) ++f;
        if (answers[i] == spt[i % 8]) ++s;
        if (answers[i] == tpt[i % 10]) ++t;
    }
    
    int M = max(max(f, s), t);
    
    vector<int> answer;
    
    if (M == f) answer.push_back(1);
    if (M == s) answer.push_back(2);
    if (M == t) answer.push_back(3);
    
    return answer;
}