Greedy1. 프로그래머스 체육복 (파이썬 풀이)

- 프로그래머스의 그리디 문제입니다.

문제

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

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

 

 

문제풀이

다음 과정으로 테스트 케이스를 오류없이 통과하였습니다.

 

- 체육복 갯수를 저장하는 배열을 만든다.

- 체육복을 왼쪽으로 줄 수 있는 경우 준다.

- 체육복을 오른쪽으로 줄 수 있는 경우 준다.

- 체육복이 1개인 학생 수를 센다.

 

이 문제를 그리디 방식으로 푼 이유는

"당장 왼쪽/오른쪽 학생에게 줄 수 있으면 준다." 를 쭉 밀고 나가면 가장 많은 학생에게 준다는 목표에 적합하기 때문입니다.

학생은 모두 독립적이고, 줄 수 있는 학생이 양쪽 뿐이기 때문에 그리디방식으로 풀 수 있습니다.

 

 

- 전체 코드

def solution(n, lost, reserve):
    answer=0
    count=[1]*(n) # 1번학생은 count[0]
    
    for i in range(len(lost)):
        count[lost[i]-1]-=1
    for i in range(len(reserve)):
        count[reserve[i]-1]+=1
    
    # 앞에 애가 없으면 준다. 처음학생은 예외.
    for i in range(n):
        if (i==0): pass
        if count[i-1]==0 and count[i]==2:
            count[i-1]=1
            count[i]=1
    
     # 뒤에 애가 없으면 준다. 맨뒤학생은 예외.
    for i in range(n):
        if (i==n-1): break
        if count[i+1]==0 and count[i]==2:
            count[i+1]=1
            count[i]=1
    
    for i in range(n):
        if(count[i]>=1):
            answer+=1
            
    return answer

 

 

-부분 코드 설명

 

1. 함수에서 사용할 answer와 count를 초기화해줍니다.

answer=0
count=[1]*(n)

answer은 최대학생을 구하여 return할 정수형 변수입니다.

가장 나중에 체육수업을 들을 수 있는 학생수를 구할 때, 반복문에서 해당되는 학생수만큼 더해주기 위한 초기화입니다.

 

count는 각 학생들이 가진 체육복의 갯수를 저장하는 리스트입니다.

모두 1개씩 가지고 있다고 가정하고, 모두 1로 초기화된 학생 수만큼 리스트를 만들어줍니다.

 

 

 

2. lost와 reserve를 이용해서 체육복의 갯수를 셋팅해줍니다.

for i in range(len(lost)):
    count[lost[i]-1]-=1
for i in range(len(reserve)):
    count[reserve[i]-1]+=1

도둑맞은 학생이 있는 리스트 lost를 훑어보며 해당하는 학생의 체육복 갯수에 1을 빼줍니다.

주의할 점은 count의 인덱스는 0부터 시작하고 학생의 번호는 1부터 시작하는 것입니다.

3번학생이 lost에 저장되어 있다면, count[2]에 3번학생의 체육복 수가 저장되어 있습니다.

 

마찬가지로 reserve에 저장된 학생은 체육복 갯수에 1을 더해줍니다.

 

 

 

3-1. 체육복을 2개 가진 학생 앞에 0개인 학생이 있다면 하나 줍니다.

for i in range(n):
    if (i==0): continue
  
    if count[i-1]==0 and count[i]==2:
        count[i-1]=1
        count[i]=1

전체 학생수만큼 for문을 반복합니다.

이때 가장 앞의 학생은 앞학생에게 줄 수 없으니 넘어가도록 합니다.

 

* if-pass: 아무동작 하지않고 밑의 코드로 내려감

* if-continue: 해당 반복을 멈추고 for문으로 돌아감

* if-break: 해당 반복을 빠져나감

 

그 후의 학생은 본인 앞 학생이 0개이고 내가 2개이면, 본인의 갯수를 하나 차감하고 앞 학생에게 하나 줍니다.

 

 

 

3-2. 이번에는 뒤 학생이 0개라면 하나 줍니다.

for i in range(n):
    if (i==n-1): break
    if count[i+1]==0 and count[i]==2:
        count[i+1]=1
    	count[i]=1

3-1과 같은 동작을 반복합니다.

하지만 가장 뒤 학생은 동작할 수 없으니 맨 뒤 학생의 인덱스 n-1에 도달하면 for문을 빠져나갑니다.

 

 

 

4. 이제 체육복을 1개 가진 모든 학생 수를 카운트합니다.

for i in range(n):
    if(count[i]>=1):
        answer+=1

체육복 갯수를 저장한 list를 돌며 1개라고 저장된 갯수를 answer에 합해줍니다.

 

끝!