[프로그래머스 C++] Greedy 체육복

첫번째 풀이

3가지 규칙을 찾아서 간단하게 풀어봤습니다.

1. 도난당한 사람 양 옆에 여유분 있는 사람이 없다면 전체 n에서 -1

2. 여유분이 있는 사람보다 도난 당한 사람이 많다면 전체 n에서 (lost-reserve)값 만큼 빼줌

3. 위 두 규칙 모두 해당될 시 큰 수만 빼줌

#include <string>
#include <vector>
 
using namespace std;
 
int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = n;
    int rule1 = 0;
    int rule2 = 0;
    vector<int> student(n);
 
    int lostL = lost.size();
    int reserveL = reserve.size();
 
 
    for (int i = 0; i < lostL; i++) {
        student[lost[i] - 1] -= 1;
    }//도난당한 사람 -1 해줌
 
    for (int i = 0; i < reserveL; i++) {
        student[reserve[i] - 1] += 1;
    }//여분있는 사람 +1 해줌
    
    //rule2 체크
    if (lostL > reserveL)
        rule2 += (lostL - reserveL);
    
    
    for (int i = 0; i < n; i++) {//rule1체크
        if (student[i] == -1) {
            if (i == 0 && student[i + 1] != 1)
                rule1++;
            else if (i == n - 1 && student[i - 1] != 1)
                rule1++;
            else
                if (i != 0 && i != n-1 && student[i - 1] != 1 && student[i + 1] != 1) {
                    rule1++;
                }
        }
    }
 
    if (rule1 > rule2)
        return answer - rule1;
    else
        return answer - rule2;
}

 

규칙을 다 찾아서 적용했다고 생각했는데 예외가 있어 다시 수정했습니다.

위에는 다시 수정해볼게요. 아래 두번째 코드 참고하시면 됩니다.

두번째 풀이

#include <string>
#include <vector>
 
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;
    }//도난당한 사람 -1 해줌
    
    for(int i = 0; i < reserve.size(); i++){
        student[ reserve[i]-1 ] += 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] += 1;
                    student[i] -= 1;
                }
            }
        }
        
        if( student[i] == 1){
            if( i + 1 < student.size()){
                if( student[i+1] == -1 ){
                    student[i+1] += 1;
                    student[i] -= 1;
                }
            }
        }
    }
    
    for(int i = 0; i< student.size(); i++){
        if( student[i] == 0 || student[i] == 1)
            ++answer;
    }
     
    
    return answer;
}

 

 

두번째 풀이 참고한 링크

https://jjeongil.tistory.com/594

C++ : 프로그래머스 : 체육복: 풀이