[programmers] Greedy - 체육복

문제

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

코딩테스트 연습 - 체육복

 

풀이

프로그래머스 그리디 문제의 첫번째 문제이다. 간단하게 문제를 소개하면, 학생들 중 체육복을 도난한 학생과 여벌의 체육복을 갖고 있는 학생이 있는데, 바로 앞번호 또는 바로 뒷번호의 학생들에게만 빌려줄 수 있다. 수업을 들을 수 있는 학생의 최댓값을 구하는 문제이다.

조건이 복잡한만큼, 각 조건들을 하나하나 고려해가면서 구현해 주기만 하면, 그리디 알고리즘으로 문제를 해결할 수 있을 것으로 보인다. 따라서 조건들을 정리해 주었다. 이때, 우선적으로 고려되어야 할 조건들부터 차례대로 정리했다.

1. 여벌 체육복을 가져온 학생이 체육복을 도난했을 경우, 본인이 사용해야 하기 때문에 체육복을 빌려줄 수 없다.
2. 앞 번호 또는 뒷 번호 학생에게만 빌려줄 수 있다.

우선 여벌 체육복을 가져왔는데 잃어버린 학생들을 찾기 위해, set을 이용하여 lost와 reserve 배열을 합치고, 해당 set에서 각각 reserve와 lost를 빼서 새로운 lost_new와 reserve_new 리스트를 만든다. 이 과정은 reserve와 lost에 겹치는 학생들의 경우 자기가 사용해야 하기 때문에, 우선 배제해주는 과정이다.

이후 앞 번호 또는 뒷 번호 학생에게만 빌려주는 과정을 거치는데, 단순하게 reserve_new 리스트를 순환하면서 1 작은 값 또는 1 큰 값이 하나라도 있으면 그 값을 lost_new 리스트에서 빼내는 방식으로 알고리즘을 작성하였다.

해당 코드를 리뷰하면서 생각해 보면, 그다지 괜찮은 코드는 아닌 것 같다. 문제에서는 n이 30 이하라고 주어져서 시간 문제는 없긴 했지만, 만약 N이 커진다면 n^2만큼의 시간 복잡도에 pop의 n만큼의 시간 복잡도까지 합쳐져 n^3의 시간 복잡도가 나타나게 된다.

아이디어만 안다면 금방 풀 수 있는 문제였지만, 나중에는 시간 복잡도까지 고려해가면서 문제를 풀 필요가 있어 보인다.

 

코드

def solution(n, lost, reserve):
    answer = 0
    lost.sort()
    reserve.sort()
    
    lost_reserve_set = set(lost + reserve)
    lost_new = list(lost_reserve_set - set(reserve))
    reserve_new = list(lost_reserve_set - set(lost))
    
    for i in reserve_new:
        j = 0
        while j < len(lost_new):
            if i-1 == lost_new[j] or i+1 == lost_new[j]:
                lost_new.pop(j)
                break
            j = j+1
            
    answer = n - len(lost_new)
    
    return answer