탐욕법(Greedy) > 체육복

• 전체 n명의 학생
• lost 벡터에 체육복 잃어버린 학생 번호 저장
• reserve 벡터에 체육복 여분 있는 학생 번호 저장
• 단, 체육복은 앞번호 혹은 뒷번호 학생에게만 대여 가능

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer=0;
    vector<int> student(n);
    
    for(int i=0;i<lost.size();i++)
    {
        student[lost[i]-1] -= 1;
    }
    
    for(int i=0;i<reserve.size();i++)
    {
        student[reserve[i]-1] += 1;
    }
    
    for(int i=0;i<n;i++)
    {
        if(student[i]==1) //지금 학생이 여벌 체육복이 있는 경우
        {
            if(i-1>-1)
            {
                if(student[i-1]==-1) //앞번호 학생이 체육복이 없는 경우
                {
                    student[i-1]++;
                    student[i]--;
                } 
            }
        }
        if(student[i]==1)
        {
            if(student[i+1]==-1) //뒷번호 학생이 체육복이 없는 경우
            {
                student[i+1]++;
                student[i]--;                    
            }
        }           
    }
    for(int i=0;i<n;i++)
    {
        if(student[i]==0||student[i]==1)
        {
            answer++;
        }
    }
    
    return answer;
}

 

 

 

---

처음에 그냥 무작정 배열에 넣어서 지우고 비교하고 복잡하게 짜다가 코드가 너무 길어져서 사실 좀 찾아봤다

다른 사람들 코드 보고 벡터로 짜는게 훨씬 쉬울거 같아서 벡터로 했다

원래 기존 벡터에서 추가/삭제 하려고 했는데 그냥 새 벡터 만들어서 거기서 lost는 -1, reserve는 +1한다

(벡터는 선언과 동시에 모두 0으로 초기화돼서 굳이 초기화 따로 안해도 됨)

 

그리고 처음에는 앞뒷번호 애들한테 체육복 빌려주는 반복문에서 그냥 현재 학생이 빌려줄수 있으면 앞번호 뒷번호 한번에 검사하려고 했는데 그러니까 테스트 케이스 오류가 났다

아마도 앞번호 이미 빌려줬는데 뒷번호 빌려줘서 그런거 같다...

그래서 if문 2개 써서 앞번호 우선으로 빌려주고 그 다음에 뒷번호 확인하는 걸로 고쳤다

그러니까 되더라...ㅎㅎ

 

기초 문법 코테랑 풀이보고 썼던거랑 다르게 이렇게 막상 풀어보니깐 생각보다 어려워서 나한테 좀 놀랐다....

아무래도 코테 연습 진짜 열심히 해야될거 같다!!!

뿌엥