[HackerRank][Python3] Priyanka and Toys

Problem :

https://www.hackerrank.com/challenges/priyanka-and-toys/problem

My Solution :

#!/usr/bin/env python3

def toys(w):

w = sorted(w)

count = 1

min_w = w[0]

i = 0

while i < n:

if min_w + 4 < w[i]:

count += 1

min_w = w[i]

i += 1

return count

n = int(input())

w = list(map(int, input().rstrip().split()))

result = toys(w)

print(result)

Comment :

처음에는 위와 같이 정렬을 먼저 하고 접근하였다. 하지만 정렬하지 않고 w가 가질 수 있는 크기만큼 list를 만들어 푸는 아래와 같은 방법도 있다. 두 방법 중 어떤 방법이 더 효율적일까? 그것은 n과 w가 가질 수 있는 값의 범위에 따라 달라진다.

My Solution2 :

#!/usr/bin/env python3

def toys(w):

containers = [0]*10001

for container in w:

containers[container] = 1

count = i = 0

while i < 10001:

if containers[i]:

count += 1

i += 4

i += 1

return count

n = int(input())

w = list(map(int, input().rstrip().split()))

result = toys(w)

print(result)