[탐욕법] 프로그래머스 L1 '체육복' (Python)

<문제 링크>

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

코딩테스트 연습 - 체육복

---

<문제 풀이>

1. 체육복을 잃어버린 학생이 여벌의 체육복이 있을 수 있다는 조건을 생각해야 함
2. 1번의 학생이 있다면 lost와 reserve에 있는 학생 번호를 지움
3. 체육수업을 들을 수 있는 학생을 구해야 하므로, 체육복을 잃어버린 학생 수를 제외하고 결괏값을 도출 (set 또는 for문을 사용할 수 있다)
4. 주어진 배열이 정렬되어있지 않을 수 있으므로 정렬
5. 여벌의 체육복을 가진 학생은 앞,뒤 번호의 학생에게만 체육복을 전달할 수 있으므로 최댓값을 도출하기 위해 앞번호부터 조건문을 실행함

<코드>

#1차 시도 실패. 3,7,12,13,14
def solution(n, lost, reserve):
    answer = 0
    answer = n-(len(lost))
    for i in lost:
        if i-1 in reserve:
            reserve.remove(i-1)
            answer += 1
        elif i+1 in reserve:
            reserve.remove(i+1)
            answer += 1
    return answer

 

#2차 시도 성공(211003 set 사용)
def solution(n, lost, reserve):
    same = []
    for i in lost:
        if i in reserve:
            same.append(i)
    reserve = list(set(reserve) - set(same))
    lost = list(set(lost)-set(same))
    
    for i in sorted(lost):
        if i-1 in reserve:
            reserve.remove(i-1)
        elif i+1 in reserve:
            print(i+1)
            reserve.remove(i+1)
        else:
            n -= 1
    return n

#2차 시도 성공 (211122 for문 사용)
def solution(n, lost, reserve):
    answer = 0
    
    tmp = []
    for i in lost:
        if i in reserve:
            tmp.append(i)
            reserve.remove(i)
    for i in tmp:
        lost.remove(i)
    
    answer = n-(len(lost))
    lost.sort()
    
    for i in lost:
        if i-1 in reserve:
            reserve.remove(i-1)
            answer += 1
        elif i+1 in reserve:
            reserve.remove(i+1)
            answer += 1
    return answer

#3차 시도 (220315 테스트케이스 참고해서 성공)
def solution(n, lost, reserve):
    answer = n - len(lost)
    reserve = sorted(reserve)
    lost = sorted(lost)
    
    for i in reserve:
        if i in lost:
            answer += 1
            lost[lost.index(i)] = 99
            reserve[reserve.index(i)] = 99
        elif i-1 in lost and i-1 not in reserve:
            answer += 1
            lost[lost.index(i-1)] = 99
            reserve[reserve.index(i)] = 99
        elif i+1 in lost and i+1 not in reserve:
            answer += 1
            lost[lost.index(i+1)] = 99
            reserve[reserve.index(i)] = 99
    
    return answer

 

 

<고쳐야 할 점>

• 체육복을 잃어버린 학생이 여벌의 체육복이 있을 수 있다는 조건을 생각해야 함
• 배열이 정렬되어 있지 않을 수 있다는 조건을 생각해야 함
• 여벌이 있는 학생과 잃어버린 학생이 같을 때 반드시 본인 꺼는 본인이 사용
• 복습 알고리즘