[그리디, 난이도 중하] 프로그래머즈, 체육복

체육복 여벌이 있는 학생들이 옆에 있는 학생에게 체육복을 빌려주었다고 했을 때

체육복을 가지고 있는 최대 학생 수를 구하면 되는 문제이다.

 

나의 풀이는 이렇다.

 

boolean 배열 2개를 생성하고 다음 조건에 맞게 true/false를 부여해야 한다.

• phy[ ] : 체육복을 1벌 이상 가지고 있는지 여부를 판단
• phy_reserve[ ] : 체육복을 2벌 가지고 있는지 여부를 판단 (여벌)

초기 bool phy[ ]는 true로 초기화 해두었다.

reserve벡터를 참조하여, 체육복을 2벌 가지고 있는 학생은 phy_reserve 배열값을 true로 만든다.

 

그리고 lost벡터를 참조하여 2가지 경우에 대해 처리해준다.

• 여벌을 가지던 학생이 도난 당하면 1벌 남으므로 phy_reserve 배열 값을 false로 바꿔준다.
• 1벌 가지고 있었던 학생이 도난 당하면 체육복이 없어지므로, phy 배열 값을 false로 한다.

이렇게 세팅을 끝내고, 1번 학생부터 다음 조건에 따라 반복문을 수행하면 된다.

자신은 여벌옷이 있고, 앞or뒷 번호의 학생이 체육복이 없다면 빌려받은 학생의 phy배열 값을 true로 한다.

단, 앞뒤 학생에게 모두 빌려줄순 없으므로 앞->뒤 순서로 탐색한다.

 

phy배열 값이 true인 학생이 몇 명인지 count하면 문제가 해결된다.

 

테스트 케이스 12개 모두 정답

 

#include <vector>
#include <string.h>
using namespace std;
bool phy[32]; //체육복을 1벌 이상 가지고있는가?
bool phy_reserve[32]; //체육복을 2벌 가지고 있는가? (여벌)
int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    memset(phy,true,sizeof(phy));
    for(int i=0;i<reserve.size();i++) phy_reserve[reserve[i]]=true;
    for(int i=0;i<lost.size();i++) {
        if(phy_reserve[lost[i]]) phy_reserve[lost[i]]=false;
        else phy[lost[i]]=false;
    }
    for(int i=1;i<n+2;i++){
        if(phy_reserve[i]){
            if(!phy[i-1]) phy[i-1]=true; //앞사람에게 여벌 줌
            else if(!phy[i+1]) phy[i+1]=true; //뒷사람에게 여벌 줌 
        }
    }
    for(int i=1;i<n+1;i++) if(phy[i]) answer++; //1벌 이상 인원 체크
    return answer;
}