[프로그래머스] 실패율 (문제 설명, 해결 과정, 코드 전문, c++)

• 문제 설명
• 해결 과정
• 코드 전문

 

문제 설명

 

 

본 문제는 프로그래머스의 실패율 문제입니다. 

오천성이란 게임이 존재하고 이 게임에는 N개의 스테이지가 존재합니다. 이 문제는 각 스테이지의 실패율을 기준으로 비교해 스테이지들을 정렬하여 반환하는 문제입니다. 스테이지의 갯수 N 말고도 플레이어들이 각자 현재 멈춰있는 스테이지 번호가 담긴 배열 stages가 주어집니다.  stages에는 1이상 N+1 이하의 숫자가 들어갑니다. (스테이지의 최고단계가 N이니 N+1은 모든 스테이지를 클리어한 유저입니다.). 실패율은 (현재 스테이지를 통과하지 못한 인원 / 현재 스테이지를 시도해 본 인원)으로 구합니다. 이제 주어진 정보로 내림차순 정렬된 결과를 반환하면 됩니다.

 

 

 

 

해결 과정

 

N+1 크기의 해쉬테이블을 만들고 stages 배열을 순회하여 해당  각 유저들이  도전했던 스테이지까지 전부 1 더해줍니다. 이제 해쉬테이블에는 스테이지별로 몇 명의 유저들이 시도했는지 알 수 있습니다. 그리고 스테이지의 수 pair배열을 만들어 first에는 실패율을 second에는 스테이지 번호를 담게합니다. 실패율을 기준으로 정렬하고 정렬한 순서대로 스테이지 번호를 반환할 것 입니다. pair배열을 채우기 위해 해쉬테이블을 전체 순회하여

 

실패율과 스테이지 번호를 넣습니다. 이 때 실패율을 구하는 공식은

현재 스테이지의 실패율 = (현재 단계를 도전했던 인원 - 다음 단계를 도전했던 인원 ) / 현재 단계를 도전했던 인원 

 

다음 단계를 도전한다는 뜻은 이전 단계는 반드시 통과했단 뜻이고 반드시 통과한 인원의 수를 그 이전 단계의 도전 했던 총 인원에서 빼면 현재 스테이지를 실패한 인원이라는 뜻입니다.

이후 실패율을 기준으로 정렬하고 정렬된 순서대로 스테이지의 번호를 반환합니다. 

 

 

 

 

코드 전문

 

 

#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

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

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<pair<double,int>> temp_map;
    unordered_map<int, int> pass_cnt_table{};
    
    for (int i=1; i <= N + 1; i++)
    {
        pass_cnt_table.insert({i,0});
    }
    
    for (auto user : stages)
    {
        for (int i=1; i <= user; i++)
        {
            pass_cnt_table[i]++;
        }
    }

    for (int i=1; i < pass_cnt_table.size(); i++)
    {
        if (pass_cnt_table[i] != 0) 
        {
            int curr_fail = pass_cnt_table[i]-pass_cnt_table[i+1];
            temp_map.push_back({(double)curr_fail / pass_cnt_table[i], i});
        }
        else {temp_map.push_back({0, i});}
    }
    
    sort(temp_map.begin(),temp_map.end(), compare);

    for (auto sorted : temp_map)
    {
        answer.emplace_back(sorted.second);
    }   
    
    return answer;
}

 

 

 

 

느낀 점 (잡설 99% , 배운점 1%(많은 편))

 

이번 문제는 꽤 재밌었습니다. 풀이 아이디어는 정말 빨리 떠올라 순조로웠는데 vector<pair> 정렬을 어떻게 해야할 지 고민하다 sort에 사용자정의 기능이 존재하여 사용해보았습니다. 카카오 인턴쉽 문제들은 1레벨이라도 쉽지가 않네요. 그래도 조금씩 성장하는 느낌은 듭니다!

 

 

 

 

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.