[programmers] Lv.1 체육복(c++)

나는 이게 왜 level1인지 이해가 안된다 ㅋㅋㅋ

내가 greedy를 잘 못하는건가?

예전에 엄청 고생해서 못풀었는데 이번에도 풀긴 풀었지만 살짝 고생해서 풀었다 ㅠ

 

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    vector<int> lost_chk(n+1, 0);
    for(int l: lost)
        lost_chk[l] = 1;
    
    vector<int> reserve_chk(n+1, 0);
    for(int r: reserve){
        if(lost_chk[r] == 1){
            lost_chk[r] = 0;
            continue;
        }
        reserve_chk[r] = 1;
    }
    
    bool repeat = true;
    vector<bool> both_side;
    while(repeat){
        both_side = vector<bool>(n+1, false);
        repeat = false;
        for(int i=1; i<=n; i++){
            if(lost_chk[i] == 0) continue;

            if(reserve_chk[i-1] == 1 && reserve_chk[i+1] == 1){
                both_side[i] = true;
            }else if(reserve_chk[i-1] == 1){
                reserve_chk[i-1] = 0;
                lost_chk[i] = 0;
                repeat = true;
            }else if(reserve_chk[i+1] == 1){
                reserve_chk[i+1] = 0;
                lost_chk[i] = 0;
                repeat = true;
            }
        }
    }
    
    for(int i=1; i<=n; i++){
        if(lost_chk[i] == 0) answer += 1;
        else if(both_side[i]) answer += 1;
    }

    return answer;
}

---

문제

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

코딩테스트 연습 - 체육복

728x90

---

[접근]

다른 사람들은 왼쪽 사람한테 있는지 확인 후 없으면 오른쪽 사람한테 확인하여 차례로 빌리는 방식을 사용했더라..

나는 음.. 그게 맞는 방법인지 헷갈렸다.

근데 다시 생각해보니 왼쪽부터 빌리면 맨 왼쪽 여분을 가진 사람은 어차피 줄 사람이 없으니 그게 최선이었던것..

하여튼 나는 좀 더 복잡하게 내 방식대로 풀어봤다.

---

[접근1]

일단 잃은 사람 번호에 체크를 해주고

잃은 사람 번호가 체크 돼있고 여분도 가지고 있다면 잃은 사람 번호에서 체크를 없애준다.

잃은 사람 번호가 체크 되어있지 않고 여분을 가지고 있다면 여분 가진 사람 번호에 체크해준다.

vector<int> lost_chk(n+1, 0);
for(int l: lost)
    lost_chk[l] = 1;

vector<int> reserve_chk(n+1, 0);
for(int r: reserve){
    if(lost_chk[r] == 1){
        lost_chk[r] = 0;
        continue;
    }
    reserve_chk[r] = 1;
}

---

[접근2]

일단 한쪽에만 여분을 가진 학생이 있으면 처리해주고, 다시 반복한다.

한쪽에만 여분을 가진 학생이 없다면, 양쪽에 여분을 가진 학생들을 체크해주고 while문을 빠져나오게한다.

bool repeat = true;
vector<bool> both_side;
while(repeat){
    both_side = vector<bool>(n+1, false);
    repeat = false;
    for(int i=1; i<=n; i++){
        if(lost_chk[i] == 0) continue;

        if(reserve_chk[i-1] == 1 && reserve_chk[i+1] == 1){
            both_side[i] = true;
        }else if(reserve_chk[i-1] == 1){
            reserve_chk[i-1] = 0;
            lost_chk[i] = 0;
            repeat = true;
        }else if(reserve_chk[i+1] == 1){
            reserve_chk[i+1] = 0;
            lost_chk[i] = 0;
            repeat = true;
        }
    }
}

---

[접근3]

정답은 잃은 학생에 체크가 되어있지 않거나, 양쪽에 여분을 가졌다고 체크되어있는 학생의 수가 정답이된다.

for(int i=1; i<=n; i++){
    if(lost_chk[i] == 0) answer += 1;
    else if(both_side[i]) answer += 1;
}