정렬) 실패율 🌙

Yona·2022년 2월 10일

알고리즘 이코테 정렬 프로그래머스

👩‍🎓 이것이 코딩 테스트다

목록 보기

23/27

문제

풀이

처음 든 생각

가장 무식한방법의 시간복잡도
- N번에 걸쳐서 실패율을 구한다음,
  정렬 하면 O(NlogN)이다.
- 결론적으로 O(NlogN)
- 1<=N<=500 이므로 시간복잡도 쌉가능
deque로 개선
- dequeue.push 와 Pop의 시간복잡도는 O(logN)이다.
- 그러므로 입력받는 순간 실패율을 계산하여 deque에 push집어넣고, pop 빼내면서 정렬된 값을 구하자!

풀이아이디어

정해진 대로 구현하기만 하면 되는 구현문제였삼

정답 코드

def solution(N, stages) :
	answer = []
	length = len(stages)

	# 스테이지 번호를 1부터 N까지 증가시키며
	for i in range(1, N+1) :
		count = stages.count(i) #해당 스테이지에 머물러있는 사람 수 계산

		# 실패율 계산
		if length == 0 :
			fail = 0
		else :
			fail = count/length
		
		# 리스트에 (스테이지 번호, 실패율) 원소 삽입
		answer.append((i, fail))
		length -= count

	# 실패율 기준으로 각 스테이지를 내림차순 정렬
	answer = sorted(answer, key=lambda t : t[1], reverse=True)

	# 결정된 스테이지 번호 출력
	answer = [i[0] for i in answer]
	return answer

내가 쓴 코드

def solution(N, stages):
    answer = []
    finished_user = stages[-1] # 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자
    
    # 딕셔너리 초기화
    stage_dict = {}
    for i in range(N+1) : 
        stage_dict[i] = 0
    for stage in stages :
        stage_dict[stage -1] += 1
        
    failure_arr = []
    # 스테이지 실패율 계산 (총 마친 사람 보정, 도달한사람 없으면 실패율 0)
    for i in range(N) :
        total_user = 0
        failure_rate = 0
        for j in range (i+1) :
            total_user += stage_dict[j] # 스테이지에 도달한 플레이어 수
        if total_user != 0 : 
            failure_rate = stage_dict[i] / total_user
        failure_arr.append(failure_rate)
        
    for i in range(N) :
        stage_dict[i] = failure_arr[i]
    

    # 내림차순 정렬
    sorted_dict = sorted(stage_dict.items(), key=lambda x: x[1], reverse=True)

    # Key값만 배열로 리턴
    for i in range(N) :
        answer.append(sorted_dict[i][0])
        
    return answer

느낀점

딕셔너리를 사용해서 만들어보기 노력했는데 훨 복잡해졌다ㅎㅎ
보통딕셔너리 쓰는게 더 깔끔해지던데요🗿
- 딕셔너리 쓰는 이유가 인덱스가 순차적이지 않고 좀 산포되어있을때
  검색속도가 더 빠르기 때문도 있는데
  이 문제의 경우 계속 1~N까지 순차적으로 훝으면서 연산해야하므로
  크게 딕셔너리를 사용한다고 해서 개선되지 않을 것같다. (다짜고나서 든생각 .. ㄱ-)
  - list 의 경우 시간이 자료의 크기 비례하여 늘어나지만 dictionary 의 경우 거의 일정한 시간으로 탐색하기 때문
- 그래도 딕셔너리는 쓸 수 있다면 왠만하면 쓰자!!