[프로그래머스][level 1] 실패율 (카카오 기출)

 

문제

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

필요 지식

•  c++ : class 
• [스테이지 번호, 실패율]로 묶인 데이터를 [실패율]로만 정렬하고자 할 때 필요
• 이때, 연산자 재정의 즉, 연산자 오버로딩으로 위를 구현할 수 있음

• sort함수 
• 일반적으로 쓸 때, sort(a,b)는 a에서b까지 오름차순으로 정렬
• sort(a,b,compare)로도 쓸 수 있음. 이때 compare은 두 개의 원소를 어떻게 비교할 것인가에 대한 함수. default값은 a<b이면 true를 리턴하는 함수. 그래서 오름차순이 default
• compare함수를 단독으로 정해줘서 내가 원하는 대로 정렬 가능

• vector

해결 방법

level은 순서대로 격파해 나가는 것.

즉, level을 시도한 사람 수는 전 level을 통과한 사람 수이므로, 

전 level 실패율을 계산했다면, 전 level 도전한 사람을 stages에서 제거하는 것이 좋다.

(계산이 수월해지기 때문)

예를들어, stages = [2, 1, 2, 6, 2, 4, 3, 3]에서 level 2를 시도한 사람만 알고 싶다면, '1'이라 되어있는 저 수를 제거해야함. stages = [2,2,6,2,4,3,3]이렇게.

하지만, 매번 stages를 돌면서 해당 번호를 삭제하기에는 O(N^2)의 시간 복잡도를 가진다.

따라서, 어차피 순서대로 격파해 나가는 것이므로, stages를 정렬해 버린다.

sort함수는 퀵sort로 하므로 O(NlogN)의 시간 복잡도를 가진다.

정렬하면, stages = [1,2,2,3,3,4,6]이 된다. 

이때 level 1의 실패율 = (1의 개수) / (stages size)가 되어 1/8

1의 개수를 확인하면서 vector stages의 제일 앞 요소를 제거해 나가면

stages = [2,2,3,3,4,6]

level 2 실패율 = (2의 개수) / (stages size) : 2/7

이런식으로 하면 된다.

또, 2의 개수를 확인하면서 vector stages의 제일 앞 요소를 제거하면

stages = [3,3,4,6]이 되고 마찬가지로 하면 됨

주의할 점

• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.
• 실패율 = 통과한 사람 수/stage수 일때, stage 수를 stage size로 볼 수 있다.
• stage size = 0 인 경우, 0으로 나눌 수 없으므로, 따로 0인 경우를 정해줘야함

• 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
• 정렬시에, 실패율이 같다면 스테이지를 비교하는 구문이 있어야 한다.

• erase로 빈 벡터가 된 후, *vector.begin()과 vector.front()는 빈 벡터가 되기 전의 값을 가리킴
• 설명 : https://monghead.blogspot.com/2020/10/error-c-vector-erase-front.html

코드

반성할 점

• erase()함수는 o(N)임. 
• erase하지말고, 배열처럼 사용하는 게 좋았을 듯. 이 경우, o(1)
• 즉, 첫 요소를 erase하는 식으로 가는 게 아니라, 그 스테이지 통과하지 못한 사람 index를 따로 세어서 index로 접근하는게 훨씬 빠름