[프로그래머스/알고kit/그리디] 체육복

탐욕법(Greedy/그리디)

---

체육복

---

문제

• 전체 학생 수 2 ~ 30
• 체육복을 1개 이상 가지고 있는 학생의 최댓값 return
• 도난당한 학생 : 바로 앞뒷번호 학생이 여유분 갖고 있을 경우 빌릴 수 있음
• 도난당한 학생은 1~n
• 여유분 갖고 있는 학생이 도난당했을 수도 있음 => 자기가 쓸 거 하나만 있어서 빌려줄 수 없음
• 여유분 갖고 있는 학생은 1~n

---

초기 전략 1

• 도난당한 학생 -1 번호가 여유분 보유하는지 확인 -> 빌리기
• 없을 경우, 도난당한 학생 +1 번호가 여유분 보유하는지 확인 -> 빌리기
• 체육복 1개 이상인 학생 수 출력

def solution(n, lost, reserve):
    ok = [i for i in range(1,n + 1)]
    for lo in ok:
        if lo in lost:
            ok.remove(lo)
            if lo-1 in reserve:
                reserve.remove(lo-1)
                ok.append(lo)
                lost.remove(lo)
            elif lo+1 in reserve:
                reserve.remove(lo+1)
                ok.append(lo)
                lost.remove(lo)
    return len(ok)

• 통과 못함

---

초기 전략 2

• 엣지 케이스 : 여유분 가져온 사람이 도난당했을 경우 자기가 써야 해서 도난당한 사람에게 빌려줄 수 없는 경우 고려함
• 도난당한 학생 -1 번호가 여유분 보유하는지 확인 -> 빌리기
• 없을 경우, 도난당한 학생 +1 번호가 여유분 보유하는지 확인 -> 빌리기
• 체육복 1개 이상인 학생 수 출력

def solution(n, lost, reserve):
    ok = [i for i in range(1,n + 1)]
    for rsv in reserve:
        if rsv in lost:
            reserve.remove(rsv)
            lost.remove(rsv)
    for lo in ok:
        if lo in lost:
            ok.remove(lo)
            if lo-1 in reserve:
                reserve.remove(lo-1)
                ok.append(lo)
                lost.remove(lo)
            elif lo+1 in reserve:
                reserve.remove(lo+1)
                ok.append(lo)
                lost.remove(lo)
    return len(ok)

• 예제는 통과함
• 전체는 통과 못 함

---

수정된 전략 (1.5h 고민 후 자료 참고)

• 엣지 케이스 : 맨 앞에 있는 사람, 맨 뒤에 있는 사람이 체육복 안 갖고 있을 경우
• 기존에는 양 옆을 모두 고려했었는데, 맨 앞/맨 뒤는 한 명에게서만 빌릴 수 있음

def solution(n, lost, reserve):
    lost.sort()
    reserve.sort()
    # ok = 학생 당 가질 수 있는 체육복 개수 리스트
    ok = [1]*(n+1)
    ok[0] = 0
    # 도난당한 경우 체육복 개수 -1
    for lo in lost:
        ok[lo] -= 1
    # 여유분 있는 경우 체육복 개수 +1
    for rsv in reserve:
        ok[rsv] += 1
    # 여유분 있는 사람이 도난당한 옆 번호에게 빌려주기
    for idx in range(1, n+1):
        # 해당 번호 학생이 체육복이 없을 경우
        if ok[idx] == 0:
            # 1번은 2번에게만 빌릴 수 있음
            if idx == 1:
                if ok[2] >= 2:
                    ok[1] += 1
                    ok[2] -= 1
            # n번은 n-1번에게만 빌릴 수 있음
            elif idx == n:
                if ok[n-1] >= 2:
                    ok[n] += 1
                    ok[n-1] -= 1
            # 만약 한 학생이 체육복을 빌릴 수 있는 두 명의 학생(앞번호와 뒷번호) 사이에 있고, 
            # 두 학생 모두 여벌의 체육복이 있다면, 
            elif idx > 1 and idx < n:
                if ok[idx-1] >= 2:
                    ok[idx] += 1
                    ok[idx-1] -= 1
                elif ok[idx+1] >= 2:
                    ok[idx] += 1
                    ok[idx+1] -= 1
    cnt = 0
    for student in range(1, n+1):
        if ok[student] >= 1:
            cnt += 1
    return cnt

• 통과함
• 참고 자료
  • 프로그래머스 질문하기
  • CodeTutor 1
  • CodeTutor 2

---

회고

  

Keep	Problem	Try
초기 전략 수립 & 구현 후 디버깅 엣지 케이스 혼자 고민해보기	양 끝 경우의 엣지 케이스를 생각해내지 못함	초기 전략 수립 시 양 끝 value 는 어떻게 처리할 것인지 생각할 수 있도록 주석으로 IDE 에 기재해두고 시작할 것