[프로그래머스] 실패율 42889 (Level 1) - C++

https://school.programmers.co.kr/learn/courses/30/lessons/42889

프로그래머스

 

📌 문제 요약

실패율의 정의는 다음과 같다.

실패율 = (해당 스테이지에 도달했지만 아직 클리어하지 못한 플레이어 수) / (해당 스테이지에 도달한 전체 플레이어 수)

• 스테이지 수 N (1 ≤ N ≤ 500)
• 사용자들이 현재 멈춰 있는 스테이지 번호 배열 stages
• 실패율이 높은 스테이지부터 내림차순 정렬
• 실패율이 같으면 스테이지 번호가 작은 것부터

❗️ 도달한 유저가 없는 스테이지의 실패율은 0

 

입출력 예

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

---

💡 접근 아이디어

핵심은 두 가지다.

 

1️⃣ 각 스테이지에 “멈춰 있는 사람 수”를 먼저 센다

vector<int> grades(N+2); for (auto s : stages) { grades[s]++; }

• grades[i] = i번 스테이지에서 실패한 사람 수
• N+1은 모든 스테이지를 클리어한 사람

---

2️⃣ 뒤에서부터 누적합으로 “도달한 사람 수”를 계산

 

앞에서부터 계산하면 매번 합을 다시 구해야 하지만,
뒤에서부터 누적하면 한 번의 루프로 해결 가능하다.

hap += grades[i]; 실패율 = grades[i] / hap

---

구현 코드

#include <string>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

bool compare(const pair<double,int>& a, const pair<double,int>& b){
    if(a.first == b.first) return a.second < b.second;
    return a.first> b.first;
    
}

vector<int> solution(int N, vector<int> stages) {
    //우선 각 스테이지에 멈춰있는 사람들의 수를 구해야함
    //실패율 = 현재 스테이지에 멈춰있는 사람 수 / 가장 높은 스테이지부터 멈춰있는 사람들의 합
    // grades (N+1) 선언

    vector<int> grades(N+2); //각 스테이지별 멈춰있는 사람 수
    for(auto s : stages){
        grades[s]++;  // stages 순회하면서 grades[stages[i]] ++해줌
        // 1~N+1까지 사람 존재
        //1-based
    }
    int hap=grades[N+1]; 
    vector<pair<double,int>> fails(N+1);  //(0,0)으로 초기화 1-based
    // 실패율 저장할 fails (N+1) & 누적합 저장할 hap 으로 뒤부터 계산
    //sort 한다고 해도 그게 몇 번째 스테이지인지 알아야 함
    //pair 활용
    for(int i=0; i<N+1;i++){
        fails[i].second=i; //인덱스 초기화 1-based
    }
    for(int i=N;i>0;i--){
        hap+=grades[i];  //N번째 스테이지 실패율 = (N번째 스테이지 사람 수)/(N번째 +N+1번째)
        if(hap==0) { // 0 division 주의
            fails[i].first = 0;
            continue; 
        }
        fails[i].first=(double)grades[i]/hap; //double 자료형 실수 주의
        
    }
    sort(fails.begin()+1,fails.end(),compare);
    
    vector<int> answer;
    for(int j=1;j<=N;j++){
        answer.push_back(fails[j].second);
    }
    return answer;
}

---

❗ 내가 놓쳤던 포인트 (81점 → 100점)

처음에는 0으로 나누는 경우를 고려하지 못했다.

fails[i].first = grades[i] / hap; // hap == 0 가능

• 특정 스테이지에 도달한 사람이 아예 없는 경우
• 문제에서 명시적으로
• “도달한 유저가 없는 경우 실패율은 0”
  이라고 되어 있었음

-> hap == 0 인 경우를 명시적으로 처리해야 한다.

---

🔍 반례 찾기 노하우 (중요)

스스로 반례를 찾기 힘들어 AI에게 "답 대신 반례 찾는 힌트"를 요청해 해결했다.
그래서 이번에 정리한 반례 찾는 체크리스트를 정리해 보았다. 

---

1️⃣ 양 끝값을 항상 의심하자

대부분의 버그는 여기서 나온다.

• 데이터가 아예 없을 때
• 데이터가 하나만 있을 때
• 분모가 0이 되는 경우
• 인덱스가 0-based인지 1-based인지

👉 헷갈리면 반드시 주석으로 명시

---

2️⃣ 정렬 조건 다시 확인하기

• 값이 같을 때의 Tie-break 기준은 명확한가?
• 문제에서 “같을 경우 ~ 순으로”라는 문구를 놓치지 않았는가?

이 문제에서는

실패율이 같으면 스테이지 번호가 작은 것부터

---

3️⃣ 데이터 타입 & 범위 체크

• int / int == int 문제 → double 캐스팅
• 숫자 범위가 커질 때 overflow 가능성
• 문제에 있는 예외 조건을 if문으로 강제 구현했는지

---

반례를 직접 만들어보는 테크닉

• 가장 작은 입력
  • N = 1, stages = [1]
  • 손으로 직접 계산 (Hand-tracing)
• 극단적인 입력
  • 모든 유저가 1단계에서 탈락
  • 모든 유저가 N+1 (전부 클리어)
• 중간에 구멍 만들기
  • 1단계: 많음
  • 2단계: 0명
  • 3단계: 다시 많음

이런 패턴은 누적합 로직이나 분모 계산에서 자주 문제를 일으킨다.

 

---

[문제 풀이 레포지토리]

https://github.com/zzmnxn/algorithm-study

GitHub - zzmnxn/algorithm-study: 알고리즘 문제 풀이 및 소스 코드 저장소