프로그래머스 완전탐색 모의고사
금방 할 줄 알았는데... 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라는 함수를 썼다. 외워둬야 겠다.
또 다른 점은 난 포인터를 썼고 이 사람은 그냥 배열 접근을 썼다는 것.