[2018 Kakao Blind] 실패율

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

코딩테스트 연습 - 실패율 | 프로그래머스

 

여태까지 풀었던 카카오 블라인드 문제중에서 가장(?) 쉬웠던 문제인것 같다.

(풀이시간이 30분 정도였음;;)

 

처음 문제를 읽었을 때는 최대 스테이지가 500, 사용자가 20만 까지로 잡혀있어서 출제자가 시간복잡도를 잘 고려해서 문제를 풀기를 원하는 문제인줄 알았다.

 

하지만, 그냥 다른 방법이 생각나지 않아 깡으로 구현했고 통과하는 것을 보고 놀랐다..

 

개인적인 생각으로 카카오 블라인드 코딩테스트는 시간복잡도에 대해 많이 관대한것 같다는 것을 느낀 문제였다...

 

- 문제 풀이

1. 2중 for문을 돌려 각 스테이지에 도달하지 못한 사람 수를 카운트 한다.

(카운트할 때의 stages 배열에 있는 값을 0으로 초기화해줘야 나중에 중복이 안생긴다.)

 

2. 카운트한 값이 0이 아닐 경우 top / bot을 해주고 bot을 top만큼 빼준다.

0일 경우 0이랑 스테이지를 fail 배열에 추가해준다.

 

3. cmp 함수를 문제에 맞게 따로 정의해서 sort 함수를 이용해 fail 배열을 정렬해준다.

 

4. 정렬된 fail 배열의 값을 answer에 넣어준다.

 

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

using namespace std;

struct PAIR {
	double fail;
	int stage;
};

vector<PAIR> fail;

bool cmp(PAIR &a, PAIR &b) {
	if (a.fail > b.fail) return true;
	else if (a.fail == b.fail) {
		return a.stage < b.stage;
	}
	else return false;
}

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    
    int bot = stages.size();

	for (int i = 1; i <= N; i++) {

		int top = 0;
		for (int j = 0; j < stages.size(); j++) {
			if (i == stages[j]) {
				top += 1;
				stages[j] = 0;
			}
		}
		if (top != 0) {
			fail.push_back({ (double)top / (double)bot, i });
		}
		else if (top == 0) {
			fail.push_back({ 0, i });
		}
		bot -= top;
	}

	sort(fail.begin(), fail.end(), cmp);

	for (int i = 0; i < fail.size(); i++) {
		answer.push_back(fail[i].stage);
	}
    
    return answer;
}