[프로그래머스/Day 14] 모의고사 - 런타임 에러와 max_element 사용 시 주의점

오늘은 프로그래머스 '모의고사' 문제를 풀며 겪었던 인덱스 초과 문제와 std::map과 max_element 사용 시의 주의점을 정리해 보았습니다.

1. 문제 개요

이 문제는 1, 2, 3번 수포자가 찍는 방식(패턴)이 정해져 있을 때, 정답 answers 배열이 주어지면 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 리턴해야 합니다.

• 가장 높은 점수를 받은 사람이 여럿일 경우, 오름차순으로 정렬해서 리턴해야 합니다.

---

2. 첫 번째 접근: 시행착오

처음에는 수포자 번호와 점수를 명시적으로 관리하기 위해 std::map<int, int>를 사용하여 직관적으로 접근했습니다. 하지만 제출 시 런타임 에러와 오답이 발생했습니다.

// ... 생략 ...
vector<vector<int>> patterns = { {1, 2, 3, 4, 5}, ... };

// 문제점 1: 반복문 내부
for(size_t t = 0; t < answers.size(); ++t) {
    if(answers[t] == patterns[0][t]) countingMap[1]++;
    // ...
}

// 문제점 2: 최대값 찾기
auto maxIt = max_element(countingMap.begin(), countingMap.end());

원인 분석 1: 인덱스 범위 초과 (Runtime Error)

가장 큰 문제는 패턴 배열에 접근하는 방식이었습니다. answers의 길이는 최대 10,000이지만, 수포자들의 패턴 길이는 5, 8, 10으로 매우 짧습니다. t가 패턴 배열의 길이보다 커지는 순간, 존재하지 않는 메모리를 참조하여 Segmentation Fault가 발생합니다.

원인 분석 2: max_element의 비교 방식 (Logic Error)

std::map의 요소는 pair<Key, Value> 형태입니다. C++의 max_element는 기본적으로 < 연산자를 사용해 대소 비교를 수행합니다. pair의 비교 방식은 첫 번째 요소(Key)를 먼저 비교하고, 같을 경우에만 두 번째 요소(Value)를 비교합니다.

 

즉, 점수(Value)가 아니라 수포자 번호(Key)가 큰 3번이 max_element로 선택될 확률이 매우 높습니다.

(예: 1번이 100점, 3번이 0점이어도 (1, 100) < (3, 0)이 true가 되어 3번이 최대값으로 판별됨)

---

3. 두 번째 접근: 오류 수정

위의 두 가지 문제를 해결하여 코드를 수정했습니다.

1. 나머지 연산자(%) 도입: 인덱스가 패턴 길이를 넘어가면 다시 0부터 시작하도록 수정.
2. 커스텀 비교 함수(Comparator) 사용: max_element가 Key가 아닌 Value(점수)를 기준으로 비교하도록 람다 함수 추가.

vector<int> solution(vector<int> answers) {
    vector<int> answer;

    // 패턴 정의
    vector<vector<int>> patterns = {
        {1, 2, 3, 4, 5},
        {2, 1, 2, 3, 2, 4, 2, 5},
        {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}
    };

    map<int, int> countingMap = {{1, 0}, {2, 0}, {3, 0}};

    // [수정 1] 나머지 연산으로 인덱스 순환
    for(size_t t = 0; t < answers.size(); ++t) {
        if(answers[t] == patterns[0][t % patterns[0].size()]) countingMap[1]++;
        if(answers[t] == patterns[1][t % patterns[1].size()]) countingMap[2]++;
        if(answers[t] == patterns[2][t % patterns[2].size()]) countingMap[3]++;
    }

    // [수정 2] Value(점수)를 기준으로 비교하도록 람다식 추가
    auto maxIt = max_element(countingMap.begin(), countingMap.end(), 
        [](const auto& a, const auto& b) {
            return a.second < b.second;
        }
    );

    // 결과 담기
    for(auto const& [key, val] : countingMap) {
        if(val == maxIt->second) answer.push_back(key);
    }

    return answer;
}

---

4. 세 번째 접근: 문제의 특성을 이용한 풀이

이 문제는 수포자가 1, 2, 3번으로 고정되어 있기 때문에 std::map을 사용할 필요가 없습니다.

vector나 배열을 사용하면 인덱스로 바로 접근이 가능하여 코드가 훨씬 간결해지고 성능도 좋아집니다.

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

vector<int> solution(vector<int> answers) {
    vector<int> answer;
    vector<int> scores(3, 0); // 0번 인덱스=1번수포자, 1번=2번, 2번=3번

    vector<vector<int>> patterns = {
        {1, 2, 3, 4, 5},
        {2, 1, 2, 3, 2, 4, 2, 5},
        {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}
    };

    // 채점
    for(size_t i = 0; i < answers.size(); ++i) {
        if(answers[i] == patterns[0][i % 5]) scores[0]++;
        if(answers[i] == patterns[1][i % 8]) scores[1]++;
        if(answers[i] == patterns[2][i % 10]) scores[2]++;
    }

    // 최대 점수 구하기 (vector라 값 비교가 직관적)
    int max_score = *max_element(scores.begin(), scores.end());

    // 최대 점수를 가진 사람 찾기
    for(int i = 0; i < 3; ++i) {
        if(scores[i] == max_score) {
            answer.push_back(i + 1); // 0번 인덱스는 1번 수포자이므로 +1
        }
    }

    return answer;
}

---

5. 정리

1. 순환하는 배열 접근: 패턴이 반복될 때는 반드시 index % size를 사용하여 인덱스 에러(Segmentation Fault)를 방지해야 한다.
2. STL 알고리즘의 기본 동작 이해: map과 같은 컨테이너에 max_element를 사용할 때는 기본 비교가 Key 기준인지 Value 기준인지 명확히 알고, 필요하면 비교 함수(Comparator)를 반드시 제공해야 한다.
3. 데이터의 크기나 범위가 고정적이라면 map 대신 vector나 array를 사용한다.