[알고리즘] 프로그래머스_실패율

본 블로그는 비상업적, 비영리적 용도의 학업만을 위해 글을 게시합니다.

1. 문제 분석

• 스테이지를 카운트하고 1스테이지부터 차례대로 실패율을 계산해나가면 될 것 같다.
• 이후 정렬을 하면 완료.

2. 문제 풀이 과정(삽질)

• 처음에 quick sort를 사용하려 했지만, 조건을 제대로 안읽어서 틀렸다.
• 같을 경우 스테이지 번호가 작은게 먼저인데, quick sort는 stable하지 않아서 merge sort로 바꿨다.
• 도달하지 못한 스테이지는 실패율을 0으로 만들어주는 것도 처음에 오류가 발생했는데, 바로 고쳤다.
• 그런데 26, 27 테스트가 오류가 계속 났다.
• C++로 푸니까 바로 풀리는데, 이유를 잘 모르겠었다.
• 코드를 몇 시간 보면서 테스트케이스를 넣으니까, N == 1일 때, 정렬이 일어나지 않으니 sorted 배열에 값이 갱신되지 않았다. 생각해보니, S에 다시 복사해주니까 sorted로 결과를 출력 안해도 되겠다.
• N == 1일 경우는 예외처리를 해주는게 카운트를 하지 않으니 좋을 것 같다.

3. 문제 해결

• 스테이지 별 잔류 인원 카운트
• 분모를 입력 사이즈로 두고 1스테이지부터 카운트/분모
• 분모 -= 카운트
• 계산한 실패율로 sort

4. 코드 (C)

#include <string>
#include <vector>

using namespace std;

typedef struct stage{
    int num;
    double people;
}Stage;

Stage S[502] = {0};
Stage sorted[502] = {0};
void init(int N)
{
    for(int i = 1; i <= N; i++)
        S[i].num = i;
    return;
}

void quickSort(int start, int end)
{
	Stage p=S[(start + end)>>1];
	int s=start;
	int e=end;

	while(s<=e)
	{
		while(S[s].people > p.people && s <= e) s++;
		while(S[e].people < p.people && s <= e) e--;

		if(s<=e)
		{
			Stage tmp = S[s];
			S[s] = S[e];
			S[e] = tmp;
			s++; e--;
		}
	}

	if(start<e) quickSort(start,e);
	if(s<end) quickSort(s, end);
}

void merge(int p, int q, int r) {
    int left = p, mid = q+1, sorted_index = p;
    while(left <= q && mid <= r) {
        if(S[left].people > S[mid].people) sorted[sorted_index++] = S[left++];
        else sorted[sorted_index++] = S[mid++];
    }
    while(left <= q) sorted[sorted_index++] = S[left++];
    while(mid <= r) sorted[sorted_index++] = S[mid++];
    for(int i = p; i <= r; i++)
        S[i] = sorted[i];
}

void mergeSort(int p, int r) {
    if(p<r) {
        mergeSort(p , (p + r) >> 1);
        mergeSort(((p + r) >> 1) + 1, r);
        merge(p, (p + r) >> 1, r);
    }
}

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    int people = 0, denominator = stages.size();
    init(N);
    
    if(N == 1)
    {
        answer.push_back(1);
        return answer;
    }
    
    for(int i = 0; i < stages.size(); i++)
        S[stages[i]].people++;
    
    for(int i = 1; i <= N; i++)
    {
        if(denominator == 0)
            break;
        people = S[i].people;
        S[i].people /= denominator;
        denominator -= people;
    }
    
    //quickSort(1, N); //unstable
    mergeSort(1, N);
        
    for(int i = 1; i <= N; i++)
        answer.push_back(S[i].num);
    
    return answer;
}

5. 코드 (C++)

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

using namespace std;

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

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<pair<int, double>> stage;
    int people = 0, denominator = stages.size();
    
    stage.push_back({0,0});
    for(int i = 1; i <= N + 1; i++)
        stage.push_back({i, 0});
    
    for(int i = 0; i < stages.size(); i++)
        stage[stages[i]].second++;
    
    for(int i = 1; i <= N; i++)
    {
        if(denominator == 0)
            break;
        people = stage[i].second;
        stage[i].second /= denominator;
        denominator -= people;
    }
    
    sort(stage.begin() + 1, stage.end() - 1, compare);
    
    for(int i = 1; i <= N; i++)
        answer.push_back(stage[i].first);
    
    return answer;