[Python/파이썬] 백준 16435번 스네이크버드

16435번: 스네이크버드

 

문제

스네이크버드는 뱀과 새의 모습을 닮은 귀여운 생물체입니다. 

스네이크버드의 주요 먹이는 과일이며 과일 하나를 먹으면 길이가 1만큼 늘어납니다.

과일들은 지상으로부터 일정 높이를 두고 떨어져 있으며 $i (1 ≤ i ≤ N)$ 번째 과일의 높이는 $h_i$입니다. 

스네이크버드는 자신의 길이보다 작거나 같은 높이에 있는 과일들을 먹을 수 있습니다.

스네이크버드의 처음 길이가 $L$일때 과일들을 먹어 늘릴 수 있는 최대 길이를 구하세요.

입력

첫 번째 줄에 과일의 개수 $N$ $(1 ≤ N ≤ 1,000)$ 과 스네이크버드의 초기 길이 정수 $L$ $(1 ≤ L ≤ 10,000)$ 이 주어집니다.

두 번째 줄에는 정수 $h_1, h_2, ..., h_N$ $(1 ≤ h_i ≤ 10,000)$ 이 주어집니다.

출력

첫 번째 줄에 스네이크버드의 최대 길이를 출력합니다.

코드

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    less, equal, greater = [], [], []
    for a in arr:
        if a < pivot:
            less.append(a)
        elif a == pivot:
            equal.append(a)
        else:
            greater.append(a)
    return quick_sort(less)+equal+quick_sort(greater)


n, l = map(int, input().split())
h = list(map(int, input().split()))

h = quick_sort(h)

for i in range(n):
    if l < h[i]:
        break
    l += 1

print(l)

 

주어진 과일들의 높이를 오름차순으로 정렬하여 낮게 위치한 과일부터 스네이크버드가 먹을 수 없을 때까지 먹으면 된다.

 

사실 내장함수 sort()를 사용하면 더 짧고 빠르게 풀이할 수 있지만, 퀵정렬을 구현해보고 싶어서 따로 구현하여 사용하였다.