[탐욕법(Greedy)] 체육복

프로그래머스

그리디로 풀면 되는 문제다.

 

체육복이 있어야 체육 수업을 들을 수 있는데, 체육복이 있는 학생 수의 최댓값을 출력하는 문제.

체육복이 없는 i번째 학생은 i-1번이나, i+1번 학생에게만 체육복을 받을 수 있다.

 

여기서 만약, i번째 학생이 i-1번째 학생에게 빌리든, i+1번째 학생에게 빌리든 체육복이 있는 학생 수는 변하지 않는다. -> 그리디

그래서 나는 만약 i번째 학생이 체육복이 없다면, i-1번째 학생에게 먼저 빌리고, 안되면 i+1번째 학생에게 빌리게 구현했다.

 

중간에 테스트 케이스 2개 정도가 계속 틀렸다고 나와서, 왜 그런지 검색해보니, lost, reserve 배열이 꼭 오름차순으로 입력되는게 아니라, 다르게 입력되는 케이스도 있다고 한다.

그래서 간단하게, lost.sort()와 reserve.sort()를 붙여줘서 해결해줬다.

 

---

def solution(n, lost, reserve):
    clothes = [1] * (n+1) # 0번 인덱스는 제외
    for l in lost:
        clothes[l] -= 1
    for r in reserve:
        clothes[r] += 1
        
    lost.sort()
    reserve.sort()
    
    for l in lost:
        if clothes[l] == 0:
            if l == 1: # 맨 앞 학생의 경우
                if clothes[l+1] == 2:
                    clothes[l] += 1
                    clothes[l+1] -= 1
            elif l == n: # 맨 뒤 학생의 경우
                if clothes[l-1] == 2:
                    clothes[l] += 1
                    clothes[l-1] -= 1
            else: # 그 외
                if clothes[l-1] == 2:
                    clothes[l] += 1
                    clothes[l-1] -= 1
                elif clothes[l+1] == 2:
                    clothes[l] += 1
                    clothes[l+1] -= 1
            
    print(clothes)
    return len([i for i in clothes[1:] if i >= 1]) # 가지고 있는 체육복의 개수가 1 이상인 학생의 수 리턴