프로그래머스 [연습문제 / 모의고사](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 42840 모의고사

---

문제 링크: https://school.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]를 반복합니다. 정답 배열이 주어질 때, 가장 많은 문제를 맞힌 사람을 오름차순으로 반환하는 문제입니다. 완전 탐색 카테고리에 속하며, 패턴 매칭과 최댓값 찾기를 활용한 시뮬레이션 문제입니다.

---

문제 해결 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> solution(vector<int> answers) {
    vector<int> answer;
    
    // 각 수포자의 답안 패턴
    int pattern1[5] = {1, 2, 3, 4, 5};
    int pattern2[8] = {2, 1, 2, 3, 2, 4, 2, 5};
    int pattern3[10] = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
    
    // 각 수포자의 정답 개수
    int score1 = 0;
    int score2 = 0;
    int score3 = 0;
    
    // 모든 문제에 대해 각 수포자의 답과 비교
    for(int i = 0; i < answers.size(); i++) {
        // 모듈로 연산으로 패턴을 반복 적용
        if(answers[i] == pattern1[i % 5]) score1++;
        if(answers[i] == pattern2[i % 8]) score2++;
        if(answers[i] == pattern3[i % 10]) score3++;
    }
    
    // 최고 점수 찾기
    int maxScore = max({score1, score2, score3});
    
    // 최고 점수를 받은 수포자들을 오름차순으로 추가
    if(maxScore == score1) answer.push_back(1);
    if(maxScore == score2) answer.push_back(2);
    if(maxScore == score3) answer.push_back(3);
    
    return answer;
}

---

코드 설명

• 핵심 알고리즘: 패턴 매칭과 완전 탐색입니다. 각 수포자의 답안 패턴을 배열로 저장하고, 모듈로 연산을 활용하여 패턴을 순환시킵니다. 모든 문제를 순회하며 각 수포자의 답과 실제 정답을 비교하여 점수를 계산합니다. 최고 점수를 구한 후, 해당 점수를 받은 수포자들을 오름차순으로 결과에 추가합니다.
• 구현 세부사항:
  • 각 수포자의 패턴을 배열로 정의합니다 (길이: 5, 8, 10).
  • score1, score2, score3 변수로 각 수포자의 정답 개수를 추적합니다.
  • i % 5, i % 8, i % 10으로 패턴의 인덱스를 순환시킵니다.
  • max 함수로 세 점수 중 최댓값을 찾습니다.
  • if 문으로 최고 점수를 받은 수포자를 순서대로 확인하여 결과에 추가합니다.
  • 수포자 번호가 1, 2, 3 순서대로 확인되므로 자동으로 오름차순 정렬됩니다.
• 시간/공간 복잡도: 시간 복잡도는 O(n)입니다. n개의 문제에 대해 각 수포자의 답을 확인하는 데 O(n)이 소요되며, 최댓값 찾기와 결과 생성은 O(1)입니다. 공간 복잡도는 O(1)로, 고정 크기의 패턴 배열과 변수만 사용하므로 입력 크기와 무관합니다.

---

실행 예시

테스트 케이스 1:

입력: answers = [1, 2, 3, 4, 5]

실행 과정:

• 1번 수포자: [1,2,3,4,5] → 5개 정답
• 2번 수포자: [2,1,2,3,2] → 2개 정답 (2번, 4번 문제)
• 3번 수포자: [3,3,1,1,2] → 2개 정답 (1번, 5번 문제)
• 최고 점수: 5점
• 결과: [1]

출력: [1]

테스트 케이스 2:

입력: answers = [1, 3, 2, 4, 2]

실행 과정:

• 1번 수포자: [1,2,3,4,5] → 2개 정답 (1번, 4번 문제)
• 2번 수포자: [2,1,2,3,2] → 2개 정답 (3번, 5번 문제)
• 3번 수포자: [3,3,1,1,2] → 2개 정답 (2번, 5번 문제)
• 최고 점수: 2점 (모두 동점)
• 결과: [1, 2, 3]

출력: [1, 2, 3]

---

결과

패턴 매칭과 모듈로 연산을 활용한 효율적인 완전 탐색 솔루션입니다. 원본 코드는 이미 최적화되어 있으며, 각 수포자의 패턴을 명확하게 표현하고 모듈로 연산으로 순환시켰습니다. 변수명을 더 명확하게 개선하고 주석을 추가하여 가독성을 향상시켰습니다. O(n) 시간 복잡도로 최대 10,000문제도 빠르게 처리할 수 있으며, 자동으로 오름차순 정렬되는 구조로 간결하게 구현했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!