[Programmers] 실패율(C++)

[프로그래머스] 실패율 문제 링크

해당 문제는 벡터와 sort 함수를 이용해 해결하였다. 구현에 주의해야 할 사항은 다음이 있다.

• 스테이지에 도달한 사람이 없는 경우 실패율이 0으로 입력되는 것에 유의한다. 즉, 실패율 계산식에서 분자에는 스테이지 클리어 실패 플레이어 수, 분모에는 스테이지 도달 플레이어 수가 들어가는데, 분모가 0이 되는 '[divide by zero] 오류 발생에 유의한다.
• 실패율에 따라 내림차순으로 정렬되지만, 같은 실패율의 스테이지 번호는 오름차순으로 정렬된다.

바로 코드를 살펴보자.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

bool comp(std::pair<float, int> var1, std::pair<float, int> var2){
    if(var1.first == var2.first){
        return var1.second < var2.second;
    }
    return var1.first > var2.first;
}

std::vector<int> solution(int N, std::vector<int> stages) {
    std::vector<int> answer(N);
    std::vector<int> reachStage(N + 1);
    std::vector<int> clearStage(N + 1);

    for(auto stage : stages){
        reachStage[stage - 1]++;
        if(stage != 1)
            clearStage[stage - 2]++;
    }
    reachStage[N - 1] += reachStage[N];
    reachStage[N] = 0;

    std::vector<std::pair<float, int>> failureRate(N);

    for(int index = N - 1; index >= 0; index--){
        reachStage[index] += reachStage[index + 1];
        clearStage[index] += clearStage[index + 1];

        if(reachStage[index] == 0){
            failureRate[index] = {0, index + 1};
        }
        else{
            failureRate[index] = {((float)(reachStage[index] - clearStage[index]) / 
                                  (float)reachStage[index]), index + 1};
        }
    }

    std::sort(failureRate.begin(), failureRate.end(), comp);
    for(int index = 0; index < N; index++){
        answer[index] = failureRate[index].second;
    }

    return answer;
}

우선 solution 함수를 들여다보자.

· 스테이지 도달, 클리어 플레이어 수 배열 만들기

이 문제를 처음 보았을 때 해당 스테이지에 도달한 플레이어 수를 구하는 것과 스테이지를 클리어한 플레이어 수를 구하는 것에서 단순 반복으로 처리하려 했다.

for (auto stage : stages) {
	for (int count = 0; count < stage - 1; count++) {
		reachStage[count]++;
		clearStage[count]++;
	}
	if (!(stage > N))
		reachStage[stage - 1]++;
}

이처럼 특정 플레이어가 n 스테이지까지 도달하였다면 reachStage 객체에서 index 0부터 n - 1까지 하나씩 더해주는 방식으로 접근한 것이다. clearStage 객체에 대해서도 똑같이 처리해주었다. 하지만 실제로 실행해보면 상당히 오랜 시간이 걸리는 것을 확인할 수 있다.

// 단순 반복 실행 결과

테스트 1 〉	통과 (0.01ms, 3.67MB)
테스트 2 〉	통과 (0.03ms, 4.11MB)
테스트 3 〉	통과 (0.84ms, 4.26MB)
테스트 4 〉	통과 (3.84ms, 6.55MB)
테스트 5 〉	통과 (11.06ms, 9.93MB)
테스트 6 〉	통과 (0.06ms, 4.12MB)
테스트 7 〉	통과 (0.28ms, 4.17MB)
테스트 8 〉	통과 (4.96ms, 6.55MB)
테스트 9 〉	통과 (17.81ms, 9.86MB)
테스트 10 〉	통과 (2.57ms, 6.42MB)
테스트 11 〉	통과 (3.47ms, 6.55MB)
테스트 12 〉	통과 (4.05ms, 8.14MB)
테스트 13 〉	통과 (10.35ms, 8.38MB)
테스트 14 〉	통과 (0.02ms, 4.1MB)
테스트 15 〉	통과 (1.34ms, 5.31MB)
테스트 16 〉	통과 (0.45ms, 4.29MB)
테스트 17 〉	통과 (1.41ms, 5.24MB)
테스트 18 〉	통과 (0.35ms, 4.36MB)
테스트 19 〉	통과 (0.09ms, 4.11MB)
테스트 20 〉	통과 (0.53ms, 4.77MB)
테스트 21 〉	통과 (0.99ms, 6.31MB)
테스트 22 〉	통과 (22.98ms, 9.84MB)
테스트 23 〉	통과 (1.75ms, 9.66MB)
테스트 24 〉	통과 (4.44ms, 9.54MB)
테스트 25 〉	통과 (0.01ms, 4.09MB)
테스트 26 〉	통과 (0.01ms, 4.11MB)
테스트 27 〉	통과 (0.01ms, 4.1MB)

n 스테이지에 도달한 플레이어는 1 스테이지부터 n 스테이지까지 거쳐왔다는 것은 자명하다. 중간 스테이지를 건너뛸 수 있다는 조건이 없다. 따라서, 3명의 플레이어가 5 스테이지에 도달하였다면 그 이전의 스테이지는 최소 3명의 플레이어가 도달했었다는 것은 당연하다. 이를 이용하여 각 스테이지에 몇 명의 플레이어가 도전 중인지를 저장한 reachStage라는 배열을 만들었다.

예를 들어 stages 매개변수에 [2, 1, 2, 6, 2, 4, 3, 3]라는 값이 주어졌다면 reachStage 배열에는 [1, 3, 2, 1, 0, 1]이라는 값이 저장된다. 1스테이지부터 각각 1명, 3명, 2명, 1명, 0명, 1명의 플레이어가 도전 중이라는 뜻이다. 그리고 마지막 인덱스부터 거꾸로 배열의 값을 더해가면 [8, 7, 4, 2, 1, 1]이라는 특정 스테이지를 거쳐간 플레이어의 수가 나온다. 그리고 해당 배열을 좌측으로 한 칸씩 당기면 해당 스테이지를 클리어한 플레이어의 수를 얻어낼 수 있다.

주의할 점은 최고 스테이지인 N 스테이지까지 클리어한 플레이어는 N + 1 스테이지에 도달한 것으로 전달되므로 reachStage[N]의 값을 reachStage[N - 1]로 옮겨주는 예외 처리가 필요하다. 이 방법으로 클리어 스테이지, 도달 스테이지 배열을 생성하면 눈에 띄게 실행 시간이 감소한 것을 확인할 수 있다.

// 수정한 배열 생성 방식 

테스트 1 〉	통과 (0.01ms, 4.1MB)
테스트 2 〉	통과 (0.02ms, 4.09MB)
테스트 3 〉	통과 (0.22ms, 4.1MB)
테스트 4 〉	통과 (0.39ms, 6.5MB)
테스트 5 〉	통과 (0.74ms, 10MB)
테스트 6 〉	통과 (0.03ms, 4.18MB)
테스트 7 〉	통과 (0.05ms, 4.11MB)
테스트 8 〉	통과 (0.38ms, 6.63MB)
테스트 9 〉	통과 (0.75ms, 9.88MB)
테스트 10 〉	통과 (0.38ms, 6.34MB)
테스트 11 〉	통과 (0.41ms, 6.59MB)
테스트 12 〉	통과 (0.52ms, 7.97MB)
테스트 13 〉	통과 (0.56ms, 8.49MB)
테스트 14 〉	통과 (0.01ms, 3.6MB)
테스트 15 〉	통과 (0.23ms, 5.22MB)
테스트 16 〉	통과 (0.29ms, 4.36MB)
테스트 17 〉	통과 (0.24ms, 5.27MB)
테스트 18 〉	통과 (0.23ms, 4.53MB)
테스트 19 〉	통과 (0.05ms, 4.1MB)
테스트 20 〉	통과 (0.30ms, 4.82MB)
테스트 21 〉	통과 (0.60ms, 6.37MB)
테스트 22 〉	통과 (0.86ms, 10MB)
테스트 23 〉	통과 (0.67ms, 9.58MB)
테스트 24 〉	통과 (0.67ms, 9.66MB)
테스트 25 〉	통과 (0.01ms, 4.17MB)
테스트 26 〉	통과 (0.01ms, 4.18MB)
테스트 27 〉	통과 (0.01ms, 3.59MB)

일부 케이스에 대해 미미하게 메모리 크기가 커지는 경우가 있었지만 오히려 메모리 크기가 작아진 케이스도 있어 메모리에 큰 영향을 끼친다고 보긴 어려울 정도였다. 중요한 것은 10ms 이상 걸리던 테스트 케이스가 있었던 이전 방법과는 달리 실행이 1ms 이상 걸리는 테스트 케이스가 없어 확실히 실행 시간이 단축된 것을 확인할 수 있다.

· 실패율 계산하기

우리는 위 방법으로 특정 스테이지를 '클리어한' 플레이어 수와 특정 스테이지에 도달한 플레이어 수를 구했다. 하지만 문제에선 특정 스테이지에 도달하였지만 '클리어하지 못 한' 플레이어 수를 이용해 실패율을 구한다.

따라서 특정 스테이지 n의 실패율 failureRate[n]은

failureRate[n] = clearStage[n] / reachStage[n]

이 아니라,

failureRate[n] = (reachStage[n] - clearStage[n]) / reachStage[n] 

이 되어야 한다. 위 코드에서 reachStage와 clearStage의 요소가 int 형으로 선언되었지만, 편의상 float으로의 형변환은 생략하였다.

그런데, 필자는 처음에 실패율을 1 - (clearStage[n] / reachStage[n]) 로 구하려고 했었다. 하지만 프로그래머스에서는 이것이 문제가 되어 여러 문제에 실패 판정을 주었다. 아직도 이 방법이 무슨 문제가 있는지 모르겠다. 사실 이것이 실패율 문제에 대한 포스트를 작성하게 한 원인이다. 진짜 뭐가 문제지.. 똑같은 수식인데 분명..

· 정렬 알고리즘

기본적으로 <algorithm> 헤더에 포함된 sort() 함수는 오름차순으로 정렬되도록 설정되어 있다. 이를 내림차순으로 정렬하려면

sort(arr.rbegin(), arr.rend());

와 같이 일반적으로 사용하는 begin(), end()와 같은 정방향 반복자가 아닌 rbegin(), rend()라는 컨테이너의 역방향 반복자를 사용하는 것이 방법이 될 수 있다. 하지만 이번 문제에선 기본적으로 내림차순으로 정렬하되, 같은 실패율의 스테이지에 대해선 오름차순으로 스테이지 번호를 정렬해야 한다. 따라서 커스텀 비교 연산을 정의해줄 필요가 있다.

bool comp(std::pair<float, int> var1, std::pair<float, int> var2){
    if(var1.first == var2.first){
        return var1.second < var2.second;
    }
    return var1.first > var2.first;
}

sort() 함수에 사용할 비교 함수는 정렬할 컨테이너와 같은 타입의 두 변수를 인자로 가진다. 그리고 반환하는 대소 비교가 참이 되도록 정렬을 해준다. 이번 문제에서 실패율 배열 failureRate의 first에는 실패율, second에는 스테이지 번호가 저장된다.

이에 따라 실패율이 같은 스테이지는 스테이지가 낮은 것이 참이 되도록 즉, 스테이지가 낮은 순서대로 정렬되며, 기본적으로는 실패율이 큰 것이 참이 되도록 즉, 실패율이 높은 순서대로 정렬된다는 뜻이다.