[프로그래머스] 체육복 Python 풀이

프로그래머스(Programmers) 체육복 문제

난이도 : Level 1

<문제 링크>

https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

 

-> greedy 탐욕법 알고리즘 이용 

<방법1>

def solution(n, lost, reserve):

    # 인덱싱 쉽게 하기 위해 전체 학생수 +2 만큼 1이 들어있는 리스트 생성

    num = [1] * (n+2)

   

    # 체육복 없는 학생 -1

    for i in lost:

        num[i] -= 1

    # 여분 체육복 있는 학생 +1

    for i in reserve:

        num[i] += 1

   # 0 ,2(체육복X, 여분O) 거나 2, 0(여분O, 체육복X)인 경우 1,1(체육복 1개존재)로 변경

    for i in range(1, n+1):

        if num[i-1] ==0 and num[i] == 2:

            num[i-1], num[i] = 1, 1

        elif num[i] == 2 and num[i+1] == 0:

            num[i], num[i+1] = 1,1

    answer = 0

    # 1인 개수 세기

    for i in num[1:-1]:

        if i == 1 or i == 2:

            answer +=1

   

    return answer

 

만약 n 학생수가 매우 큰 조건이라면?

그에 반해 여벌 체육복 가져오는 학생 수가 적다면?

-> 전체 학생 수만큼 반복하여 코드를 짜는 것을 비효율적임

 

학생들 접근시 set집합 자료형 이용 -> O(1) 상수시간 걸림

여벌의 체육복 가져온 학생 수만 고려 

-> 전체 학생 수가 많은 것에 비해 여벌 체육복 가져온 학생이 적다면 더 효율적인 알고리즘

<방법2>

def solution(n, lost, reserve):

    # 체육복 도난, 여분 있는 학생 -> 교집합

    num = set(lost) & set(reserve)

    # 체육복 없는 학생

    l = set(lost) - num

    # 체육복 여분 있는 학생 (여분 있는데 도난 안당함)

    r = set(reserve) - num

    # 체육복 여분 있는 학생(r) 정렬 후 비교

    for i in sorted(r):

        if i-1 in l: # 오름차순으로 정렬 후 번호 작은 학생 먼저 살펴보기

            l.remove(i-1)

        elif i+1 in l:

            l.remove(i+1)

    # 총학생수 - 최종 체육복 없는 학생        

    answer = n - len(l)

    return answer

 

-> 여벌의 체육복 가져온 학생을 정렬 후 반복문으로 접근했으므로 

-> 정렬된 만큼의 시간복잡도가 사용됨 

-> O(n log n) 시간복잡도