문제

탐욕법(Greedy)문제
https://programmers.co.kr/learn/courses/30/lessons/42862

---

접근

1. 학생수(n) + 2 개의 배열을 만든다. 처음 모든 학생들은 체육복을 가지고 있다는 가정하에 모두 1의 값을 갖는다.

stu = [1] * (n+2)

2. lost에 해당하는 index의 학생은 학생배열에서 -1을 한다.
3. reserve에 해당하는 index의 학생은 +1을 한다.

for i in lost:
	stu[i] -= 1
for i in reserve:
        stu[i] += 1
    

4. 앞 학생이 뒷 학생에게 체육복을 빌려주거나 뒷 학생이 앞 학생에게 체육복을 빌려주는 경우

for i in range(1,len(stu)):
        if stu[i] == 0 and stu[i-1] == 2 :
            stu[i-1] -= 1
            stu[i] += 1
        elif stu[i] == 0 and stu[i+1] == 2 :
            stu[i+1] -= 1
            stu[i] += 1

5. 따라서 맨 앞과 맨 뒤의 index를 제외한 초기배열에서, 0이 아닌 값의 수가 답이 된다.

---

코드

python

def solution(n, lost, reserve):
    stu = [1]*(n+2)
    for i in lost:
        stu[i] -= 1
    for i in reserve:
        stu[i] += 1
            
    for i in range(1,len(stu)):
        if stu[i] == 0 and stu[i-1] == 2 :
            stu[i-1] -= 1
            stu[i] += 1
        elif stu[i] == 0 and stu[i+1] == 2 :
            stu[i+1] -= 1
            stu[i] += 1
    
    result = [x for x in stu[1:-1] if x!=0]
    return len(result)
    

---

js

function solution(n, lost, reserve) {
    let stu = [];
    for(let i=0; i<n+2; i++){
        stu.push(1);
    }
    for(let i=0; i<lost.length; i++){
        stu[lost[i]] -= 1;
    }
    for(let i=0; i<reserve.length; i++){
        stu[reserve[i]] += 1;
    }
    
    for(let i=1; i<stu.length-1; i++){
        if(stu[i]==0 && stu[i-1]==2){
            stu[i-1] -= 1;
            stu[i] += 1;
        }else if(stu[i]==0 && stu[i+1]==2){
            stu[i+1] -= 1;
            stu[i] += 1;
        }
    }
    
    let result = stu.slice(1, n+1);
    return result.filter(x => x!==0).length;
    
}