프로그래머스 세 번째 문제: 실패율(Level 1)

 

 

안녕하세요. 오늘은 Level 1 문제인 실패율 문제를 풀어보려고 합니다.

 

 

이번 문제는 어떻게 접근하느냐에 따라서 시간 복잡도 관점에서 차이가 많이 있어 이 부분을 중점적으로 보려고 합니다.

 

 

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

프로그래머스

 

 

 

 

 

 

 

 

 

제가 푼 풀이:

def solution(N, stages):
    fail = {}
    
    for i in range(1, N+1):
        pass_cnt = 0
        succ_cnt = 0
        for s in stages:
            # stage가 i보다 크면 지나왔고, 해당 스테이지도 성공한 것
            if s > i:
                pass_cnt += 1
                succ_cnt += 1
            # 같기만 하면 지나오기만 한 것
            elif s == i:
                pass_cnt += 1
        
        # 한번도 안 지나간 stage는 0으로 처리해야 하므로 별도로 if문으로 뺀다
        if pass_cnt != 0:
            fail[i] = (pass_cnt - succ_cnt) / pass_cnt
        else:
            fail[i] = 0
    
    fail_rate = sorted(fail, key=lambda x: fail[x], reverse = True)
    
    return fail_rate

스테이지가 N개 있으므로, N개에 대해서 for문을 진행해야 하는 문제입니다.

 

반복문을 진행할 때, pass를 몇 명 했는지, 스테이지를 깬 사람은 몇 명인지 저장하기 위해서 변수를 설정해 줍니다.

 

그리고 결과에 대한 list인 stages에 대해서 반복문을 적용하면서, 각각이 i보다 크면 해당 stage를 지나왔고 성공한 것이므로 각각을 1개씩 올려주며, 같은 경우는 지나오기만 했으므로 pass_cnt를 하나 올려주는 방식으로 접근합니다.

 

그리고 실패율을 저장하는 dictionary인 fail에 대해서 값들을 저장해 줍니다.

 

만약 pass_cnt가 0인 경우는 해당 stage에 도달한 사람이 아무도 없으므로, 실패율을 0으로 저장합니다.

 

마지막으로 fail은 dictionary인데, 이를 for문으로 print 하면 key값이 나오게 됩니다.

 

그런데 fail의 키 값은 1, 2, 3... 등의 각 stage의 이름이므로, fail의 각 stage를 key로 잡아서 sort를 하면 문제에서 얘기하는 대로 실패율이 높은 순으로 배열을 return 할 수 있습니다.

 

하지만 위 풀이는 시간 복잡도 관점에서 간당간당하게 풀어진 케이스라, 조금 더 시간 복잡도 관점에서 생각해 볼 필요가 있어서 다양한 코드들을 참고해서 더욱 효과적인 풀이를 만들어냈습니다.

 

 

 

새로 만든 풀이:

from collections import Counter
def solution(N, stages):
    # stage 사람 수 저장
    cnt = len(stages)
    stage_dict = Counter(stages)
    failure = {}
    for i in range(1, N + 1):
        if cnt != 0: 
            # 딱 i인 경우라면 도전은 했지만 못 깬 경우니까 실패율의 분자가 됨.
            failure[i] = stage_dict[i] / cnt
            # stage i에 있는 인원은 그만큼 차감해줌(이미 해당 stage에서 count 했으니까)
            cnt -= stage_dict[i]
        else:
            failure[i] = 0
    
    # dictionary를 그냥 뽑으면 key가 나오게 된다.
    # 그래서 failure[i]를 하면 value 기준으로 sort 되고, 나오는 것은 key가 된다.
    return sorted(failure, key=lambda i: failure[i], reverse=True)

collections 패키지에 있는 Counter라는 함수는 중복된 데이터가 저장된 list에 사용하면 각 원소가 몇 번씩 나오는지 저장된 객체를 만들어 냅니다.

 

여기서 stages의 경우 중복된 값이 존재하는 경우가 많을 수 있고, 이럴 때는 굳이 모든 요소들을 다 for문으로 살펴볼게 아니라 Counter를 활용하게 되면 말 그대로 stages에 존재하는 요소의 가짓수 정도만 for문을 돌리면 되니까, 최소한 전체를 for문으로 돌리는 것보다는 시간 복잡도를 줄일 수 있게 됩니다.

 

 

그리고 풀이 아이디어 관점에서도 변경이 있었습니다.

 

먼저 stages에 있는 개수를 cnt로 저장하고, stages를 Counter 함수를 이용해서 dictionary 형태의 객체를 만들어냅니다.

 

그리고 동일하게 N개의 stage에 대해서 for문을 진행합니다.

 

cnt가 0인 경우는 해당 stage에 도달한 케이스가 0개 이므로, 이는 실패율을 0으로 저장해 줍니다.

 

그렇지 않은 경우는, stages에서 i에 해당하는 값의 개수를 실패율의 분자로 사용하고, cnt를 분모로 사용합니다.

 

저도 처음에 이 내용이 이해가 안 갔는데, 예시를 들어서 생각해 보겠습니다. (첫 번째 Test case)

 

for문에서 i가 1인 경우 (stage 1인 경우), 현재 stages에서 1인 경우가 1개 있으므로 stage_dict[1]은 1이 될 것이고, cnt는 8이 됩니다. 따라서 이 경우에는 실패율이 1/8로 계산됩니다.

 

for문에서 i가 2인 경우 (stage 2인 경우), 현재 stages에서 2인 경우가 3개 있으므로 stage_dict[2]은 3이 될 것이고, cnt는 stage 1에서 한 명 있었으니 이를 제외하고 7이 될 것입니다. 따라서 이 경우에는 실패율이 3/7로 계산됩니다.

 

여기서 stages에서 i에 해당하는 값의 개수를 실패율의 분자로 사용하는 이유는, stages에서 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타내기 때문입니다.

 

즉, 해당 스테이지를 도전하고 있는 사람의 수 이기 때문에, 이를 정의된 실패율의 분자인 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수와 동일한 것이죠.

 

그리고 여기서 카운팅 된 만큼은 전체 인원수에서 빼줘야 하므로, cnt에서 그만큼을 빼주면 됩니다.

 

 

마지막으로 실패율이 저장된 dictionary를 value 기준으로 내림차순으로 저장해 주면 정답이 됩니다.

 

 

처음 제가 풀었던 답안의 경우 시간 복잡도가 가장 높은 테스트 22에서 8116.53ms를 받았고, 개선한 답안의 경우 테스트 22에서 12.09ms를 받았으니, 거의 600배 이상 시간 복잡도 차이를 보였습니다.

 

Counter라고 하는 함수를 잘 활용하면, 여러모로 다른 문제에서도 시간 복잡도를 줄일 수 있을 것 같습니다.

 

 

오늘 문제는 여기까지 하겠습니다.