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

programmers.co.kr/learn/courses/30/lessons/42889

코딩테스트 연습 - 실패율

실패율 문제

구현 방법

먼저 입력 정보에 대해 고민해 봤습니다.

 

• N : 스테이지의 개수
• stages : 사용자가 현재 도전 중인 스테이지 번호

즉 stages 가 [2,1,2,6,2,4,3,3]이면, 1번 유저는 2번 스테이지에서 플레이 중, 2번 유저는 1번 스테이지에서 플레이 중, 3번 유저는 2번 스테이지에서 플레이 중.

 

stages의 숫자가 스테이지 개수인 N+1이면 해당 유저는 모든 스테이지를 완료한 유저입니다.

 

이런 입력 정보를 토대로 다음과 같은 로직을 생각했습니다.

 

실패율 계산 로직

 

stages 배열을 for문으로 i=0부터 탐색하며 (i=0,1,2,3,4,5...) (스테이지=1,2,3,4,5,6...)

• stages의 원소가 i+1, 즉 스테이지보다 크거나 같으면 해당 스테이지를 방문했거나, 현재 방문해 있는 유저일 것입니다.
• 쉽게 설명하면, stages의 원소가 4면, 1,2,3 스테이지를 방문했고, 현재 4번 스테이지에 방문해 있는 유저입니다.
• 이때 해당 스테이지를 방문한 유저 개수인 tryUser에 1을 더해줍니다.
• 만약 이때 stages의 원소가 i+1과 같으면 해당 스테이지를 클리어하지 못하고 있는 유저니 failUser에 1을 더해줍니다.

이를 스테이지 개수인 N만큼 반복합니다.

 

 

실패율과 스테이지 연관 짓기

 

실패율이 높은 스테이지부터 내림차순으로 배열에 담아 정답으로 제출해야 합니다.

이때 pair <double, int>를 사용해 pair의 첫 번째 원소는 실패율, 두 번째 원소는 스테이지 번호입니다.

위 로직을 통해 실패율을 구하면, 실패율을 담는 벡터에 make_pair(failRate, i+1)을 통해 실패율과 스테이지 번호를 같이 담아줍니다.

 

 

실패율로 정렬하기

 

실패율로 정렬하기 위해서 STL의 sort() 함수를 사용했습니다.

 

comp함수를 정의해줄 때, 두 개의 pair A와 B를 비교해 실패율을 먼저 비교해 높은 실패율에 우선순위를 주고, 실패율이 동일하면 스테이지 번호를 통해 순서대로 정렬하게 해 주었습니다.

 

 

※주의해야 할 점※ (테스트 케이스 6,7,9,13,24번 틀림)

 

위 내용대로 소스코드를 작성하여 제출했지만, 몇 개의 테스트 케이스에서 에러가 났습니다.

테스트 케이스 6,7,9,13,24번이 틀렸다고 나왔습니다.

 

찾아본 결과, 실패율을 구할 때 failUser/tryUser를 해주는데 0으로 나누어지는 경우를 생각하지 못했습니다.

 

예를 들어, 스테이지가 3번 스테이지까지 있고, stages 배열이 [1,1,1,1,1]이면 2,3번 스테이지에 대한 실패율을 구할 때 2,3번 스테이지를 방문한 유저가 0명이니 0으로 나누어주게 됩니다.

 

이를 위해 실패율을 구하기전에 어차피 해당 스테이지는 방문한 유저가 없어서 0/0을 해주었으니, 분모인 tryUser가 0이면 1로 변경해줘 0/1로 설정해주었습니다.

 

어차피 결과적으로 실패율은 0이니 테스트 케이스를 모두 통과했습니다.

 

위 내용의 소스코드는 아래와 같습니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

bool comp(pair<double,int> a, pair<double,int> b){
    //실패율 비교해서 정렬
    if(a.first > b.first) {
        return true;
    } //실패율 같으면 스테이지 번호 비교
    else if(a.first == b.first) {
        if(a.second< b.second) {
            return true;
        } else
            return false;
    } else
        return false;
}

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<pair<double,int>> failRateVector;
    double failRate;
    double tryUser;
    double failUser;

    //실패율 구하는 로직
    for(int i=0;i<N;i++) {
        //해당 스테이지 성공 못하는 유저
        failUser=0;
        //해당 스테이지 도전한 유저
        tryUser=0;
        for(int j =0;j<stages.size();j++) {
            if(stages[j]>=i+1) {
                tryUser++;
                if(stages[j] == i+1) {
                    failUser++;
                }
            }
        }
        //0으로 나눌때 예외처리
        if(tryUser == 0)
            tryUser=1;
        failRate = failUser/tryUser;
        failRateVector.push_back(make_pair(failRate,i+1));
    }

    sort(failRateVector.begin(), failRateVector.end(),comp);
    for(int i=0;i<N;i++) {
        answer.push_back(failRateVector[i].second);
    }
    return answer;
}