[Programmers] 23. 알고리즘 문제풀이(2): 프로그래머스 체육복

오류에 대한 지적이나 질문, 토의 환영합니다. 자유롭게 댓글 남겨주세요!.!

---

프로그래머스 체육복 풀이

• 이 문제의 경우 탐욕법(Greedy)으로 분류되어 있습니다.
• 체육복을 빌리는 방법이 바로 앞/뒤 학생에게 빌려야하기 때문에 어떤 방식을 택하느냐 선택해야 합니다.
• 정래진 순서로 살펴야 하고 정해진 순서에 따라 체육복을 빌려야 합니다.
• 최대 학생 수가 30밖에 되지 않기 때문에 순서대로 확인하며 빌려주어도 됩니다.

탐욕법 (Greedy Algorithm)

• 알고리즘의 각 단계에서, 그 순간이 최적이라고 생각되는 것을 선택하는 방법을 말합니다.
• 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때 사용할 수 있습니다.

---

체육복 문제 해답의 시간복잡도

def solution(n, lost, reserve):
    students = [1] * (n+2)
    
    for i in reserve:
        students[i] += 1
    for i in lost:
        students[i] -= 1
        
    for i in range(1, n+1):
        if students[i] == 0:
            if students[i-1] == 2:
                students[i-1:i+1] = [1, 1]
            elif students[i+1] == 2:
                students[i:i+2] = [1, 1]
    
    return len([i for i in students[1:-1] if i > 0])

• 여벌을 가져온 학생을 처리하는 부분(4~5)에서 $O(N)$의 시간이 걸립니다.
• 체육복을 잃어버린 학생을 처리하는 부분(6~7)에서 $O(N)$의 시간이 걸립니다.
• 체육복을 빌려주는 부분(9~14)에서 $O(N)$의 시간이 걸립니다.
• 숫자를 세는 부분(return ...)에서 $O(N)$의 시간이 걸립니다.

해시로 구현하기

만약,

전체 학생 수는 매우 큰데, 여벌의 체육복을 가져온 학생은 매우 적다면?

• reserve를 정렬하고, 이것을 하나하나 순서대로 확인하며 처리해야합니다.

def solution(n, lost, reserve):
    s = set(lost) & set(reserve)
    l = set(lost) - s
    r = set(reserve) - s
    
    for i in sorted(r):
        if i-1 in l:
            l.remove(i-1)
        elif i+1 in l:
            l.remove(i+1)
    
    return n - len(l)

• set() 을 만들 때, $O(N)$의 시간이 걸립니다.
• 빌려줄 수 있는 다른 학생을 해시로 만들고 정렬(sorted(r))해야 하기 때문에
  정렬하는 부분에서 $O(NlogN)$의 시간이 걸립니다.
• 빌려주는 부분에서는 for 반복문이 r의 수 만큼 반복하기 때문에 $O(N)$입니다.
• 그리고 l을 해시 set()으로 만들었기 때문에 접근(if i-1 in l:)하고 삭제하는(l.remove(i-1)) 시간은 $O(1)$ 입니다.

내 코드의 시간복잡도

def solution(n, lost, reserve):
    answer = n
    lost.sort()
    losts = lost.copy()
    
    for stu in lost:
        if stu in reserve:
            reserve.remove(stu)
            losts.remove(stu)
    
    for stu in losts:
        if stu-1 in reserve:
            reserve.remove(stu-1)
        elif stu+1 in reserve:
            reserve.remove(stu+1)
        else:
            answer -= 1
    return answer

• List lost를 정렬할 때 $O(N)$의 시간이 걸립니다.
• 잃어버린 학생 중(for stu in lost:, $O(N)$)
  • 여벌이 있는 지 확인하고(if stu in reserve:, $O(N)$),
    • 있으면 삭제(reserve.remove(stu-1), $O(N)$)하는 과정에서 모두 얽혀있기 때문에 $O(N^3)$의 시간이 걸립니다.

---

이 글은 프로그래머스 스쿨 인공지능 데브코스 과정에서 공부한 내용을 바탕으로 정리한 글입니다.