Picking Numbers

https://www.hackerrank.com/challenges/picking-numbers/problem?isFullScreen=true

Picking Numbers | HackerRank

 

나의 풀이

#!/bin/python3

import math
import os
import random
import re
import sys

def pickingNumbers(a):
    answer = 0
    a_dict = {}
    for i in a:
        if i not in a_dict:
            a_dict[i]=1
        else:
            a_dict[i]+=1

    result_a = sorted(a_dict.items(), key=lambda x:x[0])
    
    for i in range(len(result_a)-1):
        if result_a[i+1][0] == result_a[i][0]+1:
            answer = max(answer, result_a[i][1]+result_a[i+1][1])
        else:
            answer = max(answer, result_a[i][1])
    
    answer = max(answer, result_a[-1][1])
    return answer
    
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    n = int(input().strip())
    a = list(map(int, input().rstrip().split()))
    result = pickingNumbers(a)
    fptr.write(str(result) + '\n')
    fptr.close()

 

시간 복잡도

a_dict : 선형 시간 복잡도
sorted(a_dict.items(), key=lambda x:x[0]) :  선형 로그 시간 복잡도
for i in range(len(result_a)-1) : 선형 시간 복잡도
해당 알고리즘은 : 선형 로그 시간 복잡도 O(n log n)