프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제가 길기 때문에 접근법과 풀이과정에 대한 설명만 남깁니다.
처음 시도한 코드
def solution(N, stages):
fail = [0] * N # 실패율
for i in range(N):
fail[i] = [i+1, stages.count(i+1) / sum([s>=(i+1) for s in stages])]
return [i[0] for i in sorted(fail, key=lambda x:x[1], reverse=True)]처음 접근한 방식은 다음과 같다.
각 단계별 실패율을 담을 리스트 fail을 0이 담긴 길이 N의 형태로 만든다.
그다음 for문을 통해 N개의 단계별 실패율을 구한다.
오천성 게임은 1단계부터 N단계까지 이고, fail의 인덱스는 0번부터 N-1까지이다. 그러므로 1단계는 fail[0], 2단계는 fail[1]에 담기는 것을 생각해야 한다.
각 단계의 실패율은 "스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수"로 구함을 문제에서 알려주었다.
이를 쉽게 해석하기 위해 1단계를 예로 들었을 때, "1단계에 위치한 플레이어 수/1단계를 통과+위치한 플레이어 수"가 실패율이 될 수 있다.
1단계에 위치한 플레이어 수를 찾기 위해서는 stages에서 1이 몇 개인지 찾으면 된다.
그러므로 리스트에서 해당 값의 개수를 구하기 위해 count 함수를 사용하였다.
그다음으로, 1단계를 통과+위치한 플레이어 수는 1보다 크거나 같은 값이 몇 개인지 세면 된다.
stages의 모든 값을 1과 비교해 1 이상이면 True를 반환하게 하는 리스트 컴프리헨션을 작성하였고, 이 리스트를 sum 하여 True의 개수로 1단계를 통과한 플레이어 수를 구하였다.
하지만, 우리가 구해야 하는 답은 스테이지 번호를 실패율 순으로 나열해야 하는 것인데, 단지 실패율만 구하면 해당 실패율이 몇 단계인지 파악하기 어렵다고 생각했다.
이는 위에서 언급한 fail의 인덱스는 0부터 시작하고 스테이지는 1부터 시작하는 것이 원인이다.
그래서 fail[i]에 실패율을 넣을 때, 스테이지 번호와 함께 [i+1, 실패율] 형태로 넣어주었다. i+1이 해당 스테이지 번호가 된다.
실패율에 따라 내림차순 정렬을 해야 하므로 [i+1, 실패율]에서 실패율이 위치한 [1] 번 인덱스를 기준으로 정렬해 주었다.
sorted의 key에 lambda 함수를 이용하여 [1] 번 인덱스를 기준으로 정렬할 수 있게 해 주었고, 정렬된 결과에서 [0] 번 인덱스인 스테이지 번호만 리턴할 수 있게 함으로써 코드 작성을 완료하였다.
하지만, 에러가 발생하면 시간초과일 것으로 생각했던 것과는 달리 런타임 에러가 발생하였다.
이는 분명히 코드에서 원인이 발생한 것인데 어떤 경우가 런타임 에러를 불러오는지 생각해 보니, N=5, stages=[4,4,4]이면 ZeroDivisionError 발생하는 것이다.
스테이지는 5단계까지 존재하지만 세명의 플레이어들은 4단계까지만 완료했기 때문에 5단계를 통과+위치한 플레이어 수는 0명이다.
그렇기 때문에 실패율을 구하는 분모인 '통과한 플레이어 수'가 0이 되어 ZeroDivisionError가 발생한 것이다.
def solution(N, stages):
fail = [0] * N # 실패율
for n in range(N):
try:
fail[n] = [n+1, stages.count(n+1) / sum([s>=(n+1) for s in stages])]
except: # ZerodivisionError일 경우(=스테이지에 도달한 유저X) 실패율은 0
fail[n] = [n+1, 0]
print(fail)
return [i[0] for i in sorted(fail, key=lambda x:x[1], reverse=True)]ZeroDivisionError를 방지하기 위해 에러가 발생하면 except 구문을 실행하여 실패율을 0으로 정의하도록 코드를 수정하였다.
이제 더 이상 런타임 에러는 발생하지 않지만, 시간초과가 발생한다. N은 500, stages 길이는 200,000까지 가능하기 때문이다.
위 코드에서도 볼 수 있듯이 for문안에 stages를 순회하는 for문이 중첩되어 있다.
이 부분을 해결하기 위해 많은 시간을 고민해 보았다.
정답 코드
def solution(N, stages):
fail = [0] * N # 실패율
player = len(stages) # 스테이지별 유저 수
for n in range(N):
try:
fail[n] = [n+1, stages.count(n+1) / player]
except: # ZerodivisionError일 경우(=스테이지에 도달한 유저X) 실패율은 0
fail[n] = [n+1, 0]
player -= stages.count(n+1)
return [i[0] for i in sorted(fail, key=lambda x:x[1], reverse=True)]문제 조건에 stages의 모든 값은 1 이상이라고 주어진 것을 보고 무조건 모든 유저는 1단계를 꼭 하게 됨을 알게 되었다.
그래서 매번 stages를 순회하며 통과한 플레이어 수를 구하는 것보다 변수 하나를 가지고 연산하는 게 효율적일 것이라고 판단했다.
통과+위치한 플레이어 수를 의미하는 player=len(stages)로 처음 유저 수를 저장해 주었다. 처음 유저인 player는 1단계를 통과했든 못했든 경험이 있는 모든 유저로 볼 수 있다.
1이면 아직 1단계에 위치한 플레이어이고, 1 이상의 수면 이미 1단계는 해결해 다음 단계로 넘어간 유저이다.
따라서 단계(=N) 별로 for문을 돌며 매 단계마다 통과하지 못한 사람 수를 player에서 빼주면 단계별 player를 구할 수 있다.
중첩된 for문으로 인해 발생하는 시간 초과를 해결했다. 하지만 이 코드는 N이나 stages의 길이가 커지면 실행 시간은 오래 걸리는 것은 분명하다.