프로그래머스

프로그래밍/Python

donie 2020. 12. 3. 04:24

코딩테스트 연습 - 체육복

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번

programmers.co.kr

def solution(n, lost, reserve):

answer = 0

student = {}

for x in lost:

student[x] = student.get(x, 1) -1

for x in reserve:

student[x] = student.get(x, 1) +1

lost = [k for k,v in student.items() if v == 0]

reserve = [k for k,v in student.items() if v == 2]

for x in lost:

if x-1 in reserve:

reserve.remove(x-1)

answer += 1

elif x+1 in reserve:

reserve.remove(x+1)

answer += 1

if not reserve:

break

return n - len(lost) + answer

1) 시간복잡도

lost에 대해 for loop -> O(N)

reserve에 대해 for loop -> O(N)

lost를 다시 만들면서 student.items() -> O(N)

reserve를 다시 만들면서 student.items() -> O(N)

lost에 대해 for loop -> O(N)

따라서 시간 복잡도는 O(5*N) => O(N) 이다.