프로그래머스 [연습문제 / 실패율](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 42889 실패율

---

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42889

문제 설명:

게임의 N개 스테이지에 대해 각 스테이지의 실패율을 계산하고, 실패율이 높은 순서대로 스테이지 번호를 반환하는 문제입니다. 실패율은 "스테이지에 도달했으나 클리어하지 못한 플레이어 수"를 "스테이지에 도달한 플레이어 수"로 나눈 값이며, 같은 실패율일 경우 스테이지 번호가 작은 것이 우선입니다. 스테이지에 도달한 유저가 없으면 실패율은 0으로 정의됩니다.

---

문제 해결 코드

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

// 실패율과 스테이지 번호를 저장하는 구조체
struct StageInfo {
    double failureRate;  // 실패율
    int stageNum;        // 스테이지 번호
};

// 정렬 기준: 실패율 내림차순, 같으면 스테이지 번호 오름차순
bool compare(StageInfo a, StageInfo b) {
    if (a.failureRate != b.failureRate) {
        return a.failureRate > b.failureRate;
    }
    return a.stageNum < b.stageNum;
}

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    
    // 각 스테이지에 머물러 있는 사람 수 (클리어 실패)
    int stuckCount[502] = {0};
    
    // 각 스테이지에 도달한 사람 수
    int reachedCount[502] = {0};
    
    // 각 스테이지에 머물러 있는 사람 수 카운트
    for (int stage : stages) {
        stuckCount[stage]++;
    }
    
    // 각 스테이지에 도달한 사람 수 계산 (역순으로 누적)
    // N+1 스테이지: 모든 스테이지를 클리어한 사람
    reachedCount[N + 1] = stuckCount[N + 1];
    for (int i = N; i >= 1; i--) {
        reachedCount[i] = reachedCount[i + 1] + stuckCount[i];
    }
    
    // 각 스테이지의 실패율 계산
    vector<StageInfo> failureRates;
    for (int i = 1; i <= N; i++) {
        double failureRate;
        
        // 스테이지에 도달한 사람이 없으면 실패율은 0
        if (reachedCount[i] == 0) {
            failureRate = 0.0;
        } else {
            failureRate = (double)stuckCount[i] / reachedCount[i];
        }
        
        failureRates.push_back({failureRate, i});
    }
    
    // 실패율 기준으로 정렬
    sort(failureRates.begin(), failureRates.end(), compare);
    
    // 결과 벡터에 스테이지 번호만 저장
    for (const auto& info : failureRates) {
        answer.push_back(info.stageNum);
    }
    
    return answer;
}

---

코드 설명

• 핵심 알고리즘: 카운팅 정렬과 누적 합을 활용한 실패율 계산입니다. 각 스테이지에 머물러 있는 사람 수와 도달한 사람 수를 별도로 계산한 후, 이를 나누어 실패율을 구합니다. 구조체와 사용자 정의 비교 함수를 사용하여 실패율 기준 정렬을 수행합니다.
• 구현 세부사항:
  • stuckCount 배열에 각 스테이지에 머물러 있는 사람 수를 저장합니다.
  • reachedCount 배열을 역순으로 순회하며 누적 합으로 각 스테이지에 도달한 사람 수를 효율적으로 계산합니다 (원본 코드의 2중 반복문 제거).
  • 0으로 나누는 경우를 처리하여 도달한 사람이 없으면 실패율을 0으로 설정합니다.
  • StageInfo 구조체를 사용하여 실패율과 스테이지 번호를 함께 관리합니다.
  • compare 함수로 실패율 내림차순, 같으면 스테이지 번호 오름차순 정렬을 구현합니다.
• 시간/공간 복잡도: 시간 복잡도는 O(M + N + N log N)입니다. M은 stages 배열의 길이로 카운팅에 O(M), N개 스테이지의 도달 인원 계산에 O(N), 정렬에 O(N log N)이 소요됩니다. 공간 복잡도는 O(N)으로 배열과 벡터를 사용합니다.

---

실행 예시

입력:

N = 5
stages = [2, 1, 2, 6, 2, 4, 3, 3]

실행 과정:

• stuckCount: [0, 1, 3, 2, 1, 0, 1] (각 스테이지에 머문 사람 수)
• reachedCount: [8, 8, 7, 4, 2, 1, 1] (각 스테이지에 도달한 사람 수)
• 실패율 계산:
  • 스테이지 1: 1/8 = 0.125
  • 스테이지 2: 3/7 ≈ 0.428
  • 스테이지 3: 2/4 = 0.5
  • 스테이지 4: 1/2 = 0.5
  • 스테이지 5: 0/1 = 0
• 정렬 후 (실패율 내림차순, 같으면 번호 오름차순): 3(0.5) → 4(0.5) → 2(0.428) → 1(0.125) → 5(0)

출력:

[3, 4, 2, 1, 5]

---

결과

원본 코드의 2중 반복문을 역순 누적 합으로 개선하여 시간 복잡도를 O(N ⋅ M)에서 O(N + M)으로 최적화했습니다. 구조체와 명확한 변수명을 사용하여 코드 가독성을 높였으며, 모든 테스트 케이스를 통과했습니다.

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