https://programmers.co.kr/learn/courses/30/lessons/42840
문제 설명
수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 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하는 값을 오름차순 정렬해주세요.
입출력 예
| answers | return |
|---|---|
| [1,2,3,4,5] | [1] |
| [1,3,2,4,2] | [1,2,3] |
Solution
완전탐색이라는 방법이 항상 최선의 답안은 아니겠지만, 시간이 넉넉하다면 확실한 답을 찾을 수 있는 수단이 될 수 있다.
문제에서 볼 수 있다시피, 조금만 수학 공부를 열심히 했으면 좋겠다 싶은 양반들이 문제를 겁나게 찍고있다. 방식도 너무 뻔하다. (차라리 기둥을 박는 게 나을수도 있다. 혹시 모르지 답안 비율을 적당히 조절해줘서 쿼터는 맞을 수 있을지?)
자 문제의 정답이 주어졌다 치자. 각각의 아저씨들이 문제를 찍는 방식을 다시 한번 정리해보자.
- 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,2,3,4,5 중 하나다. 세 아저씨 중 가장 높은 점수를 맞은 사람을 return하면 된다.
- 첫 번째 입력은 1,2,3,4,5다. 첫 번째 아저씨가 운이 좋았다.
- 두 번째 입력은 1,3,2,4,2다. 첫 번째 아저씨 2개, 두 번째 아저씨 2개, 세 번째 아저씨 2개로 세 아저씨의 점수가 같다.
사실 알고리즘이라 할 것도 없고 정답을 입력받으면, 그대로 각각 아저씨들마다 규칙대로 정답을 입력받고 점수가 최대인 아저씨들을 분류해서 출력하는 게 다인 쉬운 문제다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int test1[5] = {1, 2, 3, 4, 5};
int test2[8] = {2, 1, 2, 3, 2, 4, 2, 5};
int test3[10] = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
vector<int> solution(vector<int> answers) {
vector<int> answer;
int score[3] = {0, };
int max_score = 0;
for (int i = 0; i < answers.size(); i++){
if (answers[i] == test1[i % 5]) score[0] += 1;
if (answers[i] == test2[i % 8]) score[1] += 1;
if (answers[i] == test3[i % 10]) score[2] += 1;
}
max_score = max(max(score[0], score[1]), score[2]);
for (int i = 0; i < 3; i++){
if (score[i] == max_score)
answer.push_back(i + 1);
}
return answer;
}간단하다. answer의 size만큼 for문을 돌린다. 그렇지만 각 아저씨들마다 사이클이 다르기 때문에 각자 사이클 만큼 체크를 하기 위해 i % 5, i % 8, i % 10 씩 계산해서 각자의 테스트 데이터와 정답을 비교한다.
그 다음 세 아저씨의 점수를 모두 비교한다. 비교하는 방법이야 다양하게 있겠지만 간단하게 max함수를 쓰는 것을 추천한다.
그 다음 도출 된 max_score와 각자 아저씨들의 점수를 비교해서 최대값 점수인 사람들을 answer vector에 넣고 리턴하면 끝이다.
어렵지는 않다. 그렇지만 구현 방법이 바로 생각나기는 힘들 문제였다.
