[프로그래머스] 모의고사 (Lv.1)
문제 링크
문제 설명
수포자 3명이 각자의 패턴으로 답을 찍는다.
실제 정답 배열 answers와 비교해 가장 많이 맞힌 사람을 반환한다.
동점자가 있으면 모두 포함, 오름차순 정렬.
- 수포자 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반복
내 풀이
각 수포자의 패턴을 vector로 정의하고, i % 패턴길이로 반복 인덱스를 계산했다.
answers를 순회하며 3명의 점수를 독립적으로 카운트한 뒤, max()로 최고 점수를 구하고 동점자를 모두 answer에 추가했다.
번호 순서대로 push_back하므로 별도 정렬 없이 오름차순이 자동으로 보장된다.
만약 순서가 보장되지 않는 경우라면 sort()를 사용하면 된다.
#include <algorithm>
sort(answer.begin(), answer.end()); // 오름차순
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> solution(vector<int> answers) {
vector<int> answer;
vector<int> s1 = {1,2,3,4,5};
vector<int> s2 = {2,1,2,3,2,4,2,5};
vector<int> s3 = {3,3,1,1,2,2,4,4,5,5};
int answersCount[3] = {0,0,0};
for(int i = 0; i < answers.size(); i++)
{
if(s1[i % s1.size()] == answers[i]) answersCount[0]++;
if(s2[i % s2.size()] == answers[i]) answersCount[1]++;
if(s3[i % s3.size()] == answers[i]) answersCount[2]++;
}
int maxCount = max({answersCount[0], answersCount[1], answersCount[2]});
if(answersCount[0] == maxCount) answer.push_back(1);
if(answersCount[1] == maxCount) answer.push_back(2);
if(answersCount[2] == maxCount) answer.push_back(3);
return answer;
}
시간복잡도 분석
순회 반복문: O(n)
최고 점수 및 결과 추가: O(1) (3명 고정)
전체: O(n)
문제 조건상 answers의 길이는 최대 10,000이므로, n = 10,000일 때 약 10,000번 연산 → 제한 시간 내 충분히 통과 가능하다.
오답노트
1. answer와 answers 혼용
반환용 벡터 answer와 입력 매개변수 answers를 혼용했다.
변수명이 비슷할 때는 선언부를 먼저 확인하는 습관이 필요하다.
2. C 스타일 배열에 .size() 사용 시도
int s1[]로 선언하고 s1.size()를 쓰려 했으나, C 스타일 배열은 멤버 함수가 없다.
.size()가 필요하면 vector<int>로 선언해야 한다.
3. 패턴 반복 인덱스를 처음에 고려하지 않음
answers의 길이가 패턴 길이를 초과할 경우를 고려하지 않았다.
i % 패턴길이로 인덱스를 계산해야 배열 범위를 벗어나지 않는다.
후기
오랜만에 코딩테스트를 하다보니 잦은 잔실수가 발생했다.
조금 더 꾸준히 준비해서 잔실수도 줄이고, 실력도 향상시킬 수 있도록 해야겠다.
그리고 코드도 조금 간소화 시킬 수 있을 것 같으니 조금 더 생각하고 풀어봐야겠다.