[프로그래머스] 실패율

[프로그래머스] 실패율 링크

내가 작성한 코드는 다음과 같다.

---

def solution(N, stages):
    answer = []
    FRbyStage = dict()
    denom = len(stages)

    for i in range(1, N+1):
        moleclue = stages.count(i)
        #if no one reached i-stage
        if denom == 0: FRbyStage[i] = 0
        else:
            FRbyStage[i] = moleclue/denom
            denom -= moleclue

    #sort by dict(hash)_value
    FRbyStage = sorted(FRbyStage.items(), key=lambda value: value[1], reverse=True)
    for key,value in FRbyStage: answer.append(key)
    return answer

---

✅ 내 코드 풀이

1. Input

def solution(N, stages):

전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages

2. Process

FRbyStage = dict()

Stage를 key, 해당 Stage에 대한 실패율을 value로 가지는 dictionary(hash-table) FRbyStage 변수를 선언해줬다.

---

denom = len(stages)

초기 denom 값은 stages 배열의 길이로 선언

---

for i in range(1, N+1):
    moleclue = stages.count(i)
    #if no one reached i-stage
    if denom == 0: FRbyStage[i] = 0
    else:
    	FRbyStage[i] = moleclue/denom
        denom -= moleclue

1단계부터 N+1단계까지 반복한다. (전체 스테이지 수만큼)
moleclue은 해당 stage에 멈춰있는 사람의 수
denom은 해당 stage를 통과한 사람의 수
FRbyStage dict에는 해당 stage의 실패율이 저장된다.

#if no one reached i-stage
if denom == 0: FRbyStage[i] = 0

아무도 해당 stage를 통과한 사람이 없을 경우, 즉 0으로 나눠지는 경우 예외처리를 해줬다.

---

#sort by dict(hash)_value
FRbyStage = sorted(FRbyStage.items(), 
key=lambda value: value[1], reverse=True)

dict자료형을 value값을 기준으로 정렬해준다.

---

for key,value in FRbyStage: answer.append(key)
return answer

sorted 함수를 사용하면 dict형에서 튜플 형태로 변환된다. 따라서 위처럼 key값만 answer 리스트에 append 하여 return 해줬다.

3. Output

다음과 같이 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 한다.

---

✅ 코드 실행시간 테스트

내 코드 test case 실행시간

테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.14ms, 10.2MB)
테스트 3 〉	통과 (64.64ms, 10.4MB)
테스트 4 〉	통과 (325.67ms, 10.8MB)
테스트 5 〉	통과 (1402.24ms, 14.8MB)
테스트 6 〉	통과 (1.17ms, 10.1MB)
테스트 7 〉	통과 (13.61ms, 10MB)
테스트 8 〉	통과 (324.58ms, 10.8MB)
테스트 9 〉	통과 (1304.15ms, 14.9MB)
테스트 10 〉	통과 (131.05ms, 10.8MB)
테스트 11 〉	통과 (340.38ms, 10.8MB)
테스트 12 〉	통과 (201.02ms, 11.3MB)
테스트 13 〉	통과 (426.82ms, 11.4MB)
테스트 14 〉	통과 (0.04ms, 10.2MB)
테스트 15 〉	통과 (10.49ms, 10.7MB)
테스트 16 〉	통과 (5.34ms, 10.3MB)
테스트 17 〉	통과 (11.40ms, 10.5MB)
테스트 18 〉	통과 (5.75ms, 10.2MB)
테스트 19 〉	통과 (1.14ms, 10MB)
테스트 20 〉	통과 (8.93ms, 10.3MB)
테스트 21 〉	통과 (17.14ms, 10.7MB)
테스트 22 〉	통과 (1080.11ms, 18.2MB)
테스트 23 〉	통과 (19.11ms, 11.7MB)
테스트 24 〉	통과 (72.51ms, 11.5MB)

---

[프로그래머스] 다른 사람 코드풀이 링크

def solution(N, stages):
    answer = []
    fail = []
    info = [0] * (N + 2)
    for stage in stages:
        info[stage] += 1
    for i in range(N):
        be = sum(info[(i + 1):])
        yet = info[i + 1]
        if be == 0:
            fail.append((str(i + 1), 0))
        else:
            fail.append((str(i + 1), yet / be))
    for item in sorted(fail, key=lambda x: x[1], reverse=True):
        answer.append(int(item[0]))
    return answer

다른 사람 코드 test case 실행시간

테스트 1 〉	통과 (0.03ms, 10.3MB)
테스트 2 〉	통과 (0.08ms, 10.3MB)
테스트 3 〉	통과 (1.86ms, 10.5MB)
테스트 4 〉	통과 (6.22ms, 10.9MB)
테스트 5 〉	통과 (12.22ms, 15MB)
테스트 6 〉	통과 (0.20ms, 10.3MB)
테스트 7 〉	통과 (0.66ms, 10.4MB)
테스트 8 〉	통과 (5.78ms, 10.8MB)
테스트 9 〉	통과 (12.05ms, 15MB)
테스트 10 〉	통과 (5.92ms, 10.9MB)
테스트 11 〉	통과 (6.20ms, 11MB)
테스트 12 〉	통과 (9.51ms, 11.4MB)
테스트 13 〉	통과 (9.88ms, 11.3MB)
테스트 14 〉	통과 (0.04ms, 10.3MB)
테스트 15 〉	통과 (4.20ms, 10.5MB)
테스트 16 〉	통과 (2.03ms, 10.4MB)
테스트 17 〉	통과 (3.99ms, 10.5MB)
테스트 18 〉	통과 (2.18ms, 10.4MB)
테스트 19 〉	통과 (0.44ms, 10.4MB)
테스트 20 〉	통과 (2.88ms, 10.4MB)
테스트 21 〉	통과 (6.65ms, 10.8MB)
테스트 22 〉	통과 (13.00ms, 18MB)
테스트 23 〉	통과 (14.31ms, 11.6MB)
테스트 24 〉	통과 (12.27ms, 11.6MB)
테스트 25 〉	통과 (0.02ms, 10.3MB)
테스트 26 〉	통과 (0.04ms, 10.3MB)
테스트 27 〉	통과 (0.02ms, 10.4MB)

내 코드의 테스트케이스 실행시간이 전반적으로 느리다.
그 원인을 알아내고 수정해보겠다.

---

✅ 원인 파악

1. count의 시간복잡도

for i in range(1, N+1):
	moleclue = stages.count(i) 
    	#count 연산은 시간복잡도 O(n)

다른 사람 코드보다 느린 주된 요인은 count 이였다.
count 연산은 리스트 전체를 탐색하므로 시간복잡도가 O(n)이고 둘러싸고 있는 for문의 시간 복잡도까지 같이 계산하면 O(n^2)이 된다.

info = [0]*(N+2)
for stage in stages: info[stage] +=1
for i in range(1, N+1):
	moleclue = info[i]

따라서 count 연산을 사용하지 않고 info라는 배열을 만들었다.

2. 쓸모 없는 value 탐색

FRbyStage = sorted(FRbyStage.items(), key=lambda value: value[1], reverse=True)
#해당 for문에서 value 값은 사용되지 않는다.
for key,value in FRbyStage: answer.append(key)
return answer

반복문에서 value는 사용되지 않기 때문에 의미가 없다. 수정한 코드는 아래와 같다.

for item in sorted(FRbyStage.items(), key=lambda value: value[1], reverse=True): answer.append(item[0])
return answer

---

✅ 최종 코드

수정한 전체 코드

def solution(N, stages):
    answer = []
    FRbyStage = dict()
    denom = len(stages)
    info = [0]*(N+2)

    for stage in stages: info[stage] +=1

    for i in range(1, N+1):
        moleclue = info[i]
        #if no one reached i-stage
        if denom == 0: FRbyStage[i] = 0
        else:
            FRbyStage[i] = moleclue/denom
            denom -= moleclue
   
    #sort by dict(hash)_value
    for item in sorted(FRbyStage.items(), key=lambda value: value[1], reverse=True): 
    	answer.append(item[0])
    return answer

수정한 코드의 수행시간은 다음과 같다.

테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.06ms, 10.2MB)
테스트 3 〉	통과 (0.73ms, 10.5MB)
테스트 4 〉	통과 (5.45ms, 10.9MB)
테스트 5 〉	통과 (11.87ms, 14.9MB)
테스트 6 〉	통과 (0.18ms, 10.2MB)
테스트 7 〉	통과 (0.58ms, 10.2MB)
테스트 8 〉	통과 (5.51ms, 11MB)
테스트 9 〉	통과 (16.41ms, 14.9MB)
테스트 10 〉	통과 (6.00ms, 10.9MB)
테스트 11 〉	통과 (5.81ms, 10.9MB)
테스트 12 〉	통과 (9.11ms, 11.4MB)
테스트 13 〉	통과 (9.71ms, 11.4MB)
테스트 14 〉	통과 (0.02ms, 10.2MB)
테스트 15 〉	통과 (6.42ms, 10.6MB)
테스트 16 〉	통과 (1.94ms, 10.3MB)
테스트 17 〉	통과 (4.10ms, 10.7MB)
테스트 18 〉	통과 (3.64ms, 10.3MB)
테스트 19 〉	통과 (0.71ms, 10.3MB)
테스트 20 〉	통과 (3.94ms, 10.5MB)
테스트 21 〉	통과 (5.65ms, 10.9MB)
테스트 22 〉	통과 (12.10ms, 18.4MB)
테스트 23 〉	통과 (12.16ms, 11.7MB)
테스트 24 〉	통과 (11.60ms, 11.7MB)
테스트 25 〉	통과 (0.01ms, 10.2MB)
테스트 26 〉	통과 (0.01ms, 10.2MB)
테스트 27 〉	통과 (0.01ms, 10.2MB)

이상으로 포스트를 마칩니다. 감사합니다 😊