Level 1 체육복 Python3

https://programmers.co.kr/learn/courses/30/lessons/42862?language=python3# 

코딩테스트 연습 - 체육복

 

최종 코드

• GitHub https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level1_체육복.py

hwayeon351/Programmers-Algorithms

def solution(n, lost, reserve):
    _lost = [l for l in lost if l not in reserve]
    _reserve = [r for r in reserve if r not in lost]
    for r in _reserve:
        f = r-1;
        b = r+1;
        if f in _lost:
            _lost.remove(f)
        elif b in _lost:
            _lost.remove(b)
    return n-len(_lost)

---

풀이 과정

풀이 시간 23분

체육복을 빌려줄 수 있는 사람을 체격순으로 탐색해서 최대한 앞이나 뒤에 체육복을 도난 당한 사람이 있다면 빌려주는 방식으로 마지막까지 탐색해야 가장 많이 빌려줄 수 있다.

즉, 체육복을 빌려주는 사람들이 앞이나 뒷 사람 중에 누구를 선택해서 빌려줘야 하는지 매번 최선의 선택을 하면서 빌려줘야하기 때문에 그리디 알고리즘을 적용할 수 있다.

또한,문제에서 학생들의 번호는 체격순으로 나열되어 있다고 되어있기 때문에 그리디 알고리즘을 적용할 수 있다.

 

여분의 체육복이 있는 i가 i-1과 i+1 중 누구에게 체육복을 빌려줘야 할지 최선의 선택을 하는 과정은 다음과 같다.

1. i-1과 i+1 둘 다 도난 당한 경우, 앞 사람인 i-1에게 체육복을 빌려준다.

i보다 앞 번호인 여분의 체육복이 있는 학생 j가 i-1에게 체육복을 빌려주지 못했다는 말이다.

이는 (1) j의 앞이나 뒤에 i-1이 존재하지 않은 경우, (2) j가 j의 앞인 j-1번에게 체육복을 빌려준 경우 중 하나에 해당하기 때문이다.

체격순으로 탐색하면서 그동안 탐색해온 작은 체구를 가진 학생들에게 체육복을 빌려준다면 현 시점에서 가장 최적의 답이 나오기 때문에 1.의 경우 앞 사람에게 먼저 체육복을 빌려주도록 한다.

 

2. i-1이 체육복이 있고, i+1은 도난 당한 경우,

이 경우 뒷사람에게 체육복을 빌려준다.

 

#체육복
def solution(n, lost, reserve):
	#여분을 가지고 있는 학생이 체육복을 도난 당한 경우 본인이 여분을 사용하므로 그 경우를 제외시켜 lost, reserve 리스트 초기화
    _lost = [l for l in lost if l not in reserve]
    _reserve = [r for r in reserve if r not in lost]
    #여분을 가지고 있는 학생을 체격 순으로 탐색
    for r in _reserve:
    	#여분을 가진 학생의 앞 사람
        f = r-1;
        #여분을 가진 학생의 뒷 사람
        b = r+1;
        #앞사람이 도난 당한 사람인 경우, 앞사람에게 빌려준다.
        if f in _lost:
        	#체육복을 빌렸으므로 lost에서 앞사람의 번호를 제거한다.
            _lost.remove(f)
        #앞사람은 도난 당하지 않았지만 뒷사람이 도난 당한 경우, 뒷사람에게 빌려준다.
        elif b in _lost:
             #체육복을 빌렸으므로 lost에서 앞사람의 번호를 제거한다.
            _lost.remove(b)
    #전체 학생 수에서 체육복을 빌리지 못한 도난 당한 사람 수를 뺀 값 return
    return n-len(_lost)
#시간복잡도 = O(N^2), 공간복잡도 = O(N)