[카카오] 2018블라인드채용 - 2번 문제(실패율)

문제 & 출처

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

'19 카카오 코딩 테스트 (C++) - YouTube

풀이과정

(1) 규칙

 

• 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
• 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

 

입력값이 [2, 1, 2, 6, 2, 4, 3, 3] 일 경우, 각 머물러있는 스테이지의 모습은 이렇습니다.

 

 

1번에 머물러 있는 사람, 2번에 머물러 있는 사람....n-1번에 머물러 있는 사람을 메모이제이션 배열(1~500)에 저장해놓고 실패율을 계산할때 사용합니다.

실패율은 D[N]/(N단계 이상의 사람 수) 입니다.

 

(2) 순서

 

pair타입 벡터를 선언합니다.(실패율은 소숫점까지 고려하므로 이를 저장할 double형, 해당 스테이지를 저장할 int형)

메모이제이션을 사용하여 실패율과 해당 스테이지를 벡터에 모두 저장한 후, 내림차순으로 sort 합니다.

이때, 실패율이 같은경우 스테이지 숫자가 작은 순서대로 출력합니다.

 

(3) 코드