[2019 KAKAO BLIND RECRUITMENT] 실패율

출처: https://programmers.co.kr/learn/courses/30/lessons/42889

코딩테스트 연습 - 실패율

---

 정렬 문제라고 마냥 쉬운 것만은 아니라는 것을 깨닫게 해준 문제입니다. 각종 정렬기법을 달달 외우는 것보다, 어떻게 해서 정렬 알고리즘을 효과적으로 이용할만한 로직을 짤 수 있는지가 더욱 관건인 듯 합니다. 특히 이 문제의 경우 세심한 부분을 신경써주지 않으면 모든 테스트 케이스를 통과할 수 없습니다. 이하는 전체 소스코드입니다.

 

def solution(n, stages):
    length = len(stages)

    table = [0] * (n + 2)
    for i in stages:
            table[i] += 1

    array =  []
    for i in range(1, n + 1):
        cnt = table[i]
        fail = cnt / (length + 1e-9)
        array.append((fail, i))
        length -= cnt 

    def quick_sort(array):
        if len(array) <= 1:
            return array

        pivot = array[0]
        tail = array[1:]

        left = [x for x in tail if x[0] > pivot[0]]
        right = [x for x in tail if x[0] <= pivot[0]]

        return quick_sort(left) + [pivot] + quick_sort(right)

    array = quick_sort(array)
    return list(map(lambda x : x[1], array))

 

해설

 스테이지의 개수가 N개, 플레이어의 수가 M명일 때 위 코드는 O(N + M + logM^2)의 복잡도로 해결할 수 있습니다.  이 문제같은 경우는 시간 제한이 따로 걸려있지는 않지만, 1초의 시간 제한을 두었다고 가정할 때 약 10만 번 정도의 연산이 걸리므로 충분히 해결 가능합니다.

 

 우선 계수정렬과 같이 테이블을 만들어, 각 스테이지마다 몇 명의 플레이어가 해결하지 못하고 있는지 저장합니다.

table = [0] * (n + 2)
for i in stages:
	table[i] += 1

 그 후 table에 저장한 데이터를 순회하며 실패율을 계산 및 array에 저장합니다. 초기화된 length에서 이전 스테이지에 머물던 사람 수를 순차적으로 빼줍니다. 이때 중요한 것은 length가 0일 경우 런타임 에러가 발생한다는 것입니다. 따라서 1) 조건 분기를 하거나 2) 매우 작은 수를 더하여 Zero Division Error에 대비해야 합니다.

array에 저장되는 형태는 (실패율, 스테이지)와 같이 튜플 형태입니다. 이는 정렬에 이은 정답 출력 과정을 용이하게 만듭니다.

array =  []

for i in range(1, n + 1):
	cnt = table[i]
	fail = cnt / (length + 1e-9)
	array.append((fail, i))
	length -= cnt 

  마지막으로 이렇게 정리한 array에 대해서 각 튜플의 첫번째 원소(실패율)를 기준으로 내림차순 정렬해주면 됩니다. 다만 저같은 경우 기본 정렬 라이브러리를 사용했을 때 '동일한 원소에 대해서 작은 숫자부터 출력한다'는 원칙에 위배되는 결과가 출력되는 것을 확인했기 때문에, 따로 퀵 정렬 함수를 구현해서 사용했습니다. 이후엔 정렬된 두번째 원소(스테이지)를 출력하면 되는 간단한 작업이므로 생략하겠습니다. 

def quick_sort(array):
	if len(array) <= 1:
		return array

	pivot = array[0]
	tail = array[1:]

	left = [x for x in tail if x[0] > pivot[0]]
	right = [x for x in tail if x[0] <= pivot[0]]

	return quick_sort(left) + [pivot] + quick_sort(right)

array = quick_sort(array)

   

정리

 결론적으로 여기서 핵심은 나누기 연산 시 Zero Division Error에 항상 유의하는 것, 혹은 나아가 발생할 오류를 예측하며 코드를 작성하는 습관을 다지는 것입니다. 또한 기본 정렬 라이브러리의 성능이 좋은 것은 사실이나, 스스로 정렬 알고리즘을 구현할 수 있는 실력은 어떤 경우에도 대처할 수 있는 유연성을 입증하는 것과 같은 듯합니다. 

 

---

추가

리스트 객체의 count 메서드를 사용하면 더 쉽게 해결할 수 있는 것을 확인하였습니다. 다음은 소스코드입니다.

 

def solution(n, stages):
    length = len(stages)
    
    array = []
    for i in range(1, n + 1):
        # count 메서드를 사용
        cnt = stages.count(i)
        fail = cnt / (length + 1e-8)
        length -= cnt
        
        array.append((fail, i))
        
    def quick_sort(array):
        if len(array) <= 1:
            return array

        pivot = array[0]
        tail = array[1:]

        left = [x for x in tail if x[0] > pivot[0]]
        right = [x for x in tail if x[0] <= pivot[0]]

        return quick_sort(left) + [pivot] + quick_sort(right)

    array = quick_sort(array)
    
    return list(map(lambda x: x[1], array))