##1.
def solution(N, stages):
answer = []
challenge = [0]*N #[0,0,0,0,0]
stages.sort()
for i in range(len(stages)):
for j in range(stages[i]):
if N>j:
challenge[j] +=1
sst = {}
for i in range(N):
if challenge[i] !=0:
sst[i+1]=stages.count(i+1)/challenge[i]
else:
sst[i+1]=0
stt = list(sorted(sst,key = lambda x:sst[x],reverse=True))
return stt
처음에는 이렇게 작성했다. 사실 아예 처음은 아니고 한 다섯번째 정도..?ㅎ (이거 난이도1 맞어..?)
맨 처음 시도는 notclear 리스트(stages.count(i+1)를 문제 번호에 맞게 입력한 리스트)와 challenge 리스트(스테이지를 시도한 사람 수를 입력한 리스트)를 만든다.
그리고 notclear/challenge값을 문제번호를 key로 하는 딕셔너리로 만든 다음, values를 기준으로 내림차순 정렬한다.
답으로 key를 출력한다.
예)
notclear = [8, 7, 4, 2, 1]
challenge = [1, 3, 2, 1, 0]
sst = {'1':1/8, '2':3/7, '3':2/4, '4':1/2, '5':0/1}
→ answer = [3,4,2,1,5]
근데 이렇게 하니까 테스트 케이스 22번에서 시간초과가 나버렸다.. 하
그래서 뇌를 두시간 동안 쥐어짰고 어찌저찌 하다보니 규칙이 보였음
##2.답안
def solution(N, stages):
answer = [] ; sst = {}
k = len(stages)
stages.sort()
for i in range(1,N+1):
h = stages.count(i)
if h > 0:
sst[i] = h/k
k -= h
else:
sst[i] = 0
return list(sorted(sst,key=lambda x:sst[x], reverse=True))
- 1번 스테이지 실패율 : 1/8
- 2번 스테이지 실패율 : 3/7
- 3번 스테이지 실패율 : 2/4
- 4번 스테이지 실패율 : 1/2
- 5번 스테이지 실패율 : 0/1
이렇게 주어졌을 때 전 차시의 (분모-분자) 값이 다음 차시에서의 분모가 된다는 것...
그거만 찾아도 나한테 어마어마한 발견이었다...!
알고리즘 길이가 엄청 줄어들었다.. 허허
그래서 분모는 더 이상 함수 필요 없이 길이로 해결할 수 있었고, 시간이 확 줄어듦과 동시에 테스트 케이스도 바로 통과했다