•
•
문제 설명 : 학생들에게 쿠키를 나눠주는 문제이다. 한정된 쿠키와 학생 정보를 확인하여 조건에 맞는 쿠키를 얼마나 줄 수 있는지 반환한다.
•
풀이 방법
◦
우선 제공된 배열이 정렬이 안되어 있기 때문에, 정렬이 필요하다.
▪
커서(포인터)를 옮기며 크기별로 순차 탐색을 하려고 하기 때문
◦
이후 조건에 맞을 경우에만 다음 학생을 탐색하며, 쿠키는 1회 순회마다 다음 쿠키를 확인하도록 한다.
◦
조건에 맞으면 해당 쿠키는 더 이상 다른 학생에게 주지 않기 때문에, 조건에 맞아도 조건에 맞지 않아도 쿠키는 무조건 1탐색 → 1증가이다.
•
시간복잡도 :
•
성공 코드
# O(N + NlogN) -> O(NlogN)
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g_cursor = 0
s_cursor = 0
result = 0
# 비교를 위해 정렬
# O(2 * NlogN) -> O(NlogN)
g.sort()
s.sort()
# 커서가 배열 내 범위를 벗어나지 않도록 조건 추가
while g_cursor < len(g) and s_cursor < len(s):
# 조건에 만족할 때
# 다음 아이로 설정 & 다음 쿠키부터 추가 탐색
if g[g_cursor] <= s[s_cursor]:
result += 1
g_cursor += 1
# 다음 쿠키를 찾아본다
s_cursor += 1
return result
Python
복사