[프로그래머스] 실패율

출처: 2019 KAKAO Blind Recruitment

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

코딩테스트 연습 - 실패율

실패율

문제의 자세한 설명과 제한사항은 링크에서 직접 확인하시기 바랍니다.

 

정렬을 이용하는 상황을 공부하던 중 마주한 문제인데,

정렬과 구현이 합쳐진 듯한 인상을 주길래 좋은 문제인 것 같아서 가지고 왔습니다.

 

문제에서 주어지는 입력을 정리해 보았습니다.

 

1. N: 스테이지의 개수, 1 <= N <= 100
2. stages: 각 사용자가 현재 도전 중인 스테이지의 번호.
   1. 1 <= stages.size() <= 200,000
   2. 1 <= stages[0] <= N+1, N+1은 해당 사용자가 모든 스테이지를 클리어했음을 의미

문제에서 주어진 목표는, 실패율이 높은 순서대로 stage를 정렬한 후, 정렬된 결과의 stage 번호를 출력하는 것입니다. 이 때, stage의 실패율이 같은 경우 더 낮은 stage 번호를 출력하도록 합니다.

실패율은 (스테이지에 도달하였으나 클리어 하지 못한 유저 수 / 도달한 유저 수) 로 정의합니다.

 

저는 이렇게 접근하였습니다.

맨 처음, 전체 유저의 수는 stages.size()와 같습니다. 이를 total_users라는 변수에 저장합니다.

다음으로, stages 전체를 훑으며 해당 stage까지만 도달한 유저의 수를 셉니다. 즉, 다음 stage에 도달하지 못하였으므로, 실패율의 분자 (스테이지에 도달하였으나 클리어 하지 못한 유저의 수)가 됩니다.

이를 total_users로 나누어, 실패율을 구합니다.

마지막으로, total_users를 갱신합니다. 전체 유저 수에서, 클리어 하지 못한 유저의 수를 빼면, 해당 스테이지를 클리어 한 유저의 수를 얻을 수 있습니다.

 

위 과정을 모두 진행한 후, 실패율을 내림차순으로 정렬한 다음, 해당 실패율을 가지는 스테이지를 순서대로 출력하면 됩니다.

 

본 문제를 풀면서, 제가 주목한 점은 크게 세 가지입니다.

 

1. 소수점 계산에 double 사용하기

vector에서 실패율을 담당하는 부분을 double로 처리하였지만, 계산 결과 (fail = cnt / total_users) 가 0으로 나오는 현상을 경험하였습니다.

이는 두 변수가 모두 int형이기 때문에 일어나는 일인데, 따라서 앞에 (double)을 붙여 이를 해결하였습니다.

간단하지만, 코딩테스트 실전에서 간과하기 쉬운 문제라고 생각합니다.

 

2. <algorithm>의 count 함수

제가 써본 적 없는 함수인데, 상당히 편리한 것 같습니다. 벡터의 특정 범위 내에서 원하는 원소가 출현한 횟수를 세어 return해 줍니다. 저는 int cnt = count(stages.begin(), stages.end(), i) 에서 사용하여, 1부터 N+1까지 만 도달한 유저들의 수를 세었습니다.

 

3. 비교함수 cmp의 작성

제가 작성한 비교함수는 다음과 같습니다.

bool cmp(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;
}

C++ 기준으로, 특정한 비교함수 없이 sort 함수를 사용할 경우 오름차순으로 정렬합니다. 위와 같이 pair의 경우, pair.first를 기준으로 오름차순 정렬하며, 둘이 같을 경우 pair.second의 오름차순 정렬을 합니다.

따라서 실패율이 같을 경우에 대한 처리가 별도로 없어도 문제가 없겠지만, 문제의 요구사항인 만큼 작성하였습니다.