프로그래머스 - 체육복

1. 문제

programmers.co.kr/learn/courses/30/lessons/42862

코딩테스트 연습 - 체육복

 

2. 소스코드 (Python3)

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

 

3. 고찰

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) 이다.