Cut the sticks

https://www.hackerrank.com/challenges/cut-the-sticks/problem?isFullScreen=true

Cut the sticks | HackerRank

 

나의 코드

#!/bin/python3

import math
import os
import random
import re
import sys
from collections import deque

def cutTheSticks(arr):
    answer = []
    arr= deque(sorted(arr))

    while arr:
        answer.append(len(arr))
        now_min_sk = arr.popleft()
        now_queue = deque()
        
        for i in arr:
            if i-now_min_sk > 0:
                now_queue.append(i-now_min_sk)
                
        arr = now_queue
    return answer
    
    
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    n = int(input().strip())
    arr = list(map(int, input().rstrip().split()))
    result = cutTheSticks(arr)
    fptr.write('\n'.join(map(str, result)))
    fptr.write('\n')
    fptr.close()

 

시간 복잡도

sorted(arr) :  파이썬 정렬 알고리즘 ( 선형 로그 시간 복잡도 )
while arr :  조건 만족시까지 순회 ( 선형 시간 복잡도 )
    for i in arr: arr을 배열을 순회하며 나무 길이 줄여주기 ( 선형 시간 복잡 )

해당 알고리즘 시간복잡도는 이차형 시간 복잡도 ( O(n**2) )