[2019 카카오 코딩테스트] 실패율(파이썬3) / 자체 해설 및 풀이

 

 

 

지난 '오픈채팅방/후보키' 문제에 이어

2019 카카오 코딩테스트 '실패율' 문제를

파이썬으로 풀어봤다.

 

 

⬇2019/09/01 - [알고리즘/심심풀이 문제풀기] - [2019 카카오 코딩테스트] 후보키 (파이썬3) / 자체 해설 및 풀이

[2019 카카오 코딩테스트] 후보키 (파이썬3) / 자체 해설 및 풀이

 

 

 

파이썬은 미리 갖추어져 있는 모듈이 많아서

생각하는 로직대로 알고리즘을 만들기 편하다ㅎㅎㅎ

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

---

 

자체 해설

 

시간초과로 테스트 케이스하나가 말썽을 부려서 고생한 문제이다.

 

처음 시도한 방법은 초반에 stages와 N으로 이중For문을 만드는

방식으로 구현했지만 시간제한으로 실패했다.

아래의 제한사항의 내용을 보니 이중 반복문에서 걸리는 듯하다.

 

• 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
• stages의 길이는 1 이상 200,000 이하이다.

 

 

 

 

 

 

실패율 구하기

1. 성공, 시도, 실패 배열을 만든다.
2. 게임에 참여한 총 인원 수를 저장해둔다.
3. stages 배열의 값을 보면 배열에 저장되어 있는 숫자들은 사실 실패한 스테이지이다.
4. 성공한 스테이지는 배열에 저장되어있는 값 -1 이다.
   ex) stages = [2,1,2,6,2,4,3,3] 일 때, stages[0]는 2이다.
   즉, 2 스테이지를 시도했지만 실패했다, 실제 성공은 1 스테이지까지만 한게 된다.
5. 스테이지별로 반복을 돌려 필요한 값을 얻어낸다.
6. 반복부 끝에 스테이지에 머물러있는 사람들을 변수하나에 누적시켜서 실패자의 총합을 갖고 있는다.
7. n스테이지 성공자 수  구하는 공식
   len(stages배열) /* 총 게임 참여자 수 */
      - stages배열.count(n)   /* n스테이지 실패자 */
      - { (n-1 스테이지 실패자 ) + (n-2 스테이지 실패자) + ... + (0 스테이지 실패자) }  /* 0~n-1 스테이지 실패자 합 */
8.  시도 배열[n] = 성공자배열[n] + 실패자배열[n] 

 

 

 

 

작성 코드

def solution(N, stages):
    answer = []
    successCount = [0 for i in range(0,N)]
    tryCount = [0 for i in range(0,N)]
    failCount = [0 for i in range(0,N)]
    sumFailPeople = 0
    totalPeople = len(stages)
    for stage in range(1, N+1):
        failCount[stage-1] = stages.count(stage)
        successCount[stage-1] = totalPeople - failCount[stage-1] - sumFailPeople
        tryCount[stage-1] = successCount[stage-1] + failCount[stage-1]
        sumFailPeople += failCount[stage-1]
    result = [{'idx' : idx, 'fail' : f, 'try' : tryCount[idx]} for idx, f in enumerate(failCount)]
    failRatio = []
    for i in result:
        value = 0
        if i['fail'] != 0:
            value = i['fail']/i['try']
        failRatio.append({'idx' : i['idx'], 'value' : value})
    answer =[v['idx']+1 for v in sorted(failRatio, key=lambda x: x['value'], reverse=True)]
    return answer

 

 

 

 

 

 

 

 

참고 (시간 제한 오류난 케이스)

def solution(N, stages):
    answer = []
    successCount = [0 for i in range(0,N+1)]
    tryCount = [0 for i in range(0,N+1)]
    for man in stages:
        for i in range(0,man):
            tryCount[i] += 1
            if i != man-1:
                successCount[i] += 1
    failCount = [tryCount[idx]-i for idx,i in enumerate(successCount)]
    result =  [{'idx':idx,'fail':f,'try':tryCount[idx]} for idx,f in enumerate(failCount) if idx != len(failCount)-1]
    failRatio = []
    for i in result:
        value = 0
        if i['fail'] != 0:
            value = i['fail']/i['try']
        failRatio.append({'idx' : i['idx'], 'value' : value})
    answer =[v['idx']+1 for v in sorted(failRatio, key=lambda x: x['value'], reverse=True)]
    return answer

 

 

 

카카오 공식 해설 : https://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/

 

 

 

---

 

 

도움이 되셨다면

로그인이 필요 없는 공감 버튼 꾹 눌러주세요!