[Lv 1] 체육복

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

프로그래머스

 

이 문제는 그리디 알고리즘을 사용하는 문제이다.

학생은 1번부터 30번까지 존재한다. 따라서 st배열을 할당해서 1 ~ 30까지 인덱스를 통해 학생이 체육복을 가지고 있는지 확인한다.

 

lost 배열에 존재하는 학생 번호는 1감소시키고, reserve 배열에 존재하는 학생 번호는 1증가시킨다.

이러면 체육복을 잃어버린 학생은 음수가 될 것이고, 체육복의 여분을 가지고 있는 학생은 양수가 될 것이다.

또한 체육복을 잃어버리고, 여분을 가지고 있는 학생의 경우 0이 될 것이다.

 

학생 1번부터 n번 까지 순회하며 음수인 학생에 대해 조사를 시작한다.

i번째 학생의 앞뒤 학생중 하나가 양수인 경우 i번째 학생과 앞뒤 학생을 0으로 초기화하여 더이상 빌릴 수 없게한다.

 

마지막으로 학생 배열의 값이 0이상인 경우 체육 시간에 참여할 수 있도록 한다.

 

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int st[31];

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    for(int i = 0;i<lost.size();i++){
        st[lost[i]]--; 
    }
    for(int i = 0;i<reserve.size();i++){
        st[reserve[i]]++; 
    }
    
    for(int i = 1; i <= n; i++){
        if(st[i] == -1){
            if(st[i - 1] == 1){
                st[i - 1] = 0;
                st[i] = 0;
            }
            else if(st[i + 1] == 1){
                st[i + 1] = 0;
                st[i] = 0;
            }
        }   
            
        if(st[i] >= 0) answer++;
    }
    return answer;
}