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

💡 15. 프로그래머스 체육복 문제

프로그래머스

코딩테스트 연습 - 체육복

문제

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

 

 

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

 

입출력 예

lost	reserve	return
[2, 4]	[1, 3, 5]	5
[2, 4]	[3]	4
[3]	[1]	2

입출력 예 설명

예제 #11번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #23번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

 

 

---

💡나의 문제 풀이

문제 이해

• 바로 앞번호 학생, 바로 뒷번호 학생에게만 체육복 빌려줄 수 있음
• 체육복을 적절히 빌려, 최대한 많은 학생이 체육 수업을 들어야 함
  • n: 전체 학생수 (2<=n<=30)
  • lost 배열: 도난 당한 학생들 번호 (1 <=len(lost)<=n)
  • reserve: 여벌 체육복 있는 학생들 번호 (1 <=len(reserve)<=n)
• 여벌 체육복 가져온 학생이 체육복을 도난 당할 수도 있다
• -> lost, reserve의 번호 중복 가능
• solution 함수 작성
  • 체육 수업 들을 수 있는 학생 최댓값 return

---

문제 해결 아이디어

• list 리스트 → 도난 당했지만 다시 체육복을 입을 수 있게된 학생들 번호

1. lost를 순회하며, lost와 reserve 중복되는 것을 먼저 제거

→ 여벌 체육복을 가져온 학생이 체육복 도난 가능. 자신의 것을 입는 것으로 설정

→ 중복이 가능한 것은 list 리스트에 삽입

1. lost에 남은 학생 번호 -> reserve에서 빌려줄 수 있다면 제
2. 현재 남아있는 lost 개수에서 list개수를 빼면, 최종적으로 체육복을 못 입는 학생의 수를 구하게 됨

 

---

고려 사항

• 체육복을 입을 수 있는 최대 학생을 구하는 것이므로 배열에 대한 정렬이 중요

 

 

---

작성 코드

• sort()가 필수적이다 → 최대한 앞번호가 뒷번호 학생에게 체육복을 빌려줄 수 있도록 한다. 테스트 케이스에서 정렬이 안되어 있는 경우, 체육복을 빌려줄 수 있음에도 못 빌려주는 경우가 생기기 때문
• del 말고, remove() 함수를 사용하도록 하자.

# 체육복 문제 재 도전 (테스트케이스 20/20 통과)

def main():
    print(solution(5,[2,3,4],[3,4,5])==4)
    print(solution(5, [2,4], [1,3,5])==5)
    print(solution(5, [2,4],[3])==4)
    print(solution(3,[3],[1])==2)

def solution(n, lost, reserve):
    answer = 0
    list=[] # 빌린 학생의 번호

        lost.sort()
        reserve.sort()

    # lost, reserve 중복 제거
    for i in lost:
        if i in reserve:
            list.append(i)
            del reserve[reserve.index(i)]

    # 빌려줄 수 있는 학생
    for i in lost:
        # 앞번호에게 빌리기
        if i-1 in reserve:
            if i not in list:
                list.append(i)
                del reserve[reserve.index(i-1)]
        # 뒷번호에게 빌리기
        elif i+1 in reserve:
            if i not in list:
                list.append(i)
                del reserve[reserve.index(i+1)] 

    answer = n-(len(lost)-len(list))
    return answer

main()

 

 

---

 

답안 코드

• 가장 간단하고 짧아 보이는 코드를 참고하였다.
• 가장 먼저 answer에, lost 수만큼 n에서 뺀 초기 체육복 착용 가능한 학생수를 담는다.
• lost를 순회하며
  • lost에 있는 요소가 reserve에 몇 개 있는지 확인하고 answer증가
    • reserve에 i 번호가 있다면
    • i의 앞번호가 1개 이상인 경우
    • i의 뒷번호가 1개 이상이라면

def solution(n, lost, reserve):
    answer = 0 
    answer = n - len(lost)
    for i in lost:
        if reserve.count(i) > 0:
            reserve.remove(i)
            answer += 1
        elif reserve.count(i-1) > 0:
            reserve.remove(i-1)
            answer += 1
        elif reserve.count(i+1) > 0:
            reserve.remove(i+1)
            answer += 1

    return answer

나랑 비슷하게 푸신 분 코드

def solution(n, lost, reserve):
    lost=sorted(lost)
    reserve=sorted(reserve)
    save=0
    for l in lost:
        if l in reserve:
            save+=1
            reserve.remove(l)
            continue
        for r in reserve:
            if abs(l-r)<=1 and (r not in lost):
                save+=1
                reserve.remove(r)
                break
    return (n-(len(lost)-save))

 

 

---

 

리뷰 및 점검

• 리스트.remove(i) 함수
• 파이썬 del / remove( )함수 _ 파이썬 삭제, 제거 함수
• 리스트.count(i) 함수: 찾고자 하는 항목 i가 리스트에 몇 개 있는지 반환
• 파이썬 리스트(Python List) count() 와 len()
• 처음에 풀었던 방법은 터무니 없이 비효율적인 코드였다..
  • N명 학생만큼의 리스트를 만들어서, 해당 리스트를 순회하며 lost도 확인하고 reserve도 확인하는 매우 비효율적인 코드.
• lost, reserve 배열이 정렬되어 있는 것이 아니므로, 이에 대해서도 고려를 해야하는 문제였다.