프로그래머스 실패율 파이썬 // 최대값이 200,000*500이면 시간복잡도를 의심하라, 파이썬 딕셔너리 초기화 방법, 리스트 역순정렬, 딕셔너리 for 순회

코딩테스트 연습 - 실패율 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

* 제한사항이 200,000이면 시간터진다

- 제한사항

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

 

문제 : 최악 500개스테이지, 200,000 길이이면

각각 스테이지돌면서 1~200,000까지 카운팅 ->1억 -> 터짐

해결 : #해결 : 현재어디에 몇명인는지 저장(노클리어에 이미저장됨)
    #ex) 스테이지2:3명 -> 도달사람수[스테이지2]+=3
    #이렇게하면 탐색할 스테이지수가(500) 줄어서 1억이안넘을것임!

 

* 의사코드

- 노클리어 : {스테이지, 못깬사람수}

-도달사람수:{스테이지, 도달사람수(클리어포함)}

1. for stage :

노클리어[n]++

2. for 노클리어 :

(노클리어{스테이지2 : 3}이면 -> 3명은 스테이지1은 깻다는거임 ->카운팅)

while(key--):

도달사람수[key]++

 

* 파이썬 딕셔너리 초기화 방법

for i in range(10):
    노클리어.setdefault(i, 0)

ex)노클리어.setdefault (0,10)

#키값0이 존재하면 pass(포인터를 반환한다고 함),

키값0이없다면 10으로 초기화하라.

 

* 리스트 역순정렬

key=lambda x: - x[1]  //앞에 -1 곱하면됨

list=sorted(list,key=lambda x:-x[1])

 

* 딕셔너리 for 순회

딕셔너리.items() 하면 각각 순회가능!

for key,value in 노클리어.items():

 

def solution(N, stages):
    answer = []
    노클리어=dict()
    도달사람수=dict()
    
    # for i in range(504):
    #     노클리어[i]=0
    #     도달사람수[i]=0
    ######해쉬맵초기화#############
    #my_dict.setdefault(key, 0)
    #없을때만 맵에추가해줌
    
    for i in range(N+1):
        노클리어.setdefault(i+1, 0)
        도달사람수.setdefault(i+1, 0)
        
    for stage in stages:
        #노클리어.setdefault(stage, 0)
        노클리어[stage]+=1
        
        ########################
        #최악 : 스테이지수=500, 스테이지길이=200,000이면
        #1억이라 터짐
        # for i in range(stage):
        #     #도달사람수.setdefault(i+1, 0)
        #     도달사람수[i+1]+=1
    #해결 : 현재어디에 몇명인는지 저장(노클리어에 이미저장됨)
    #ex) 스테이지2:3명 -> 도달사람수[스테이지2]+=3
    #이렇게하면 탐색할 스테이지수가(500) 줄어서 1억이안넘을것임!
    #stages=sorted(stages)
    
    for key,value in 노클리어.items():
        while(key>0):
            도달사람수[key]+=value
            key-=1
            
        
        
    #print(stages)
            
    print("노클리어: ",노클리어)
    print("도달사람수: ",도달사람수)
    
    #딕셔너리 순회방법
    #딕셔너리.items()
    list=[]
    for key,value in 도달사람수.items():
        pass
        노클리어.setdefault(key,0)
        if 도달사람수[key]==0:
            list.append([key,0])
            continue
        list.append([key,노클리어[key]/도달사람수[key]])
    
    print(list)
    
    list=sorted(list,key=lambda x:-x[1])
    print(list)
    
    # for i in range(len(answer)+1,N+1):
    #     list.append([i,0])
    
    for v in list:
        if v[0]>N:
            continue;
        answer.append(v[0])
    
    

        
        
    return answer