체육복 C++(그리디,탐욕법)[프로그래머스]

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소입니다.

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

코딩테스트 연습 - 체육복 | 프로그래머스

 

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

4. 결과

---

1. 문제 설명

 

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

 

문제!!

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

전체 학생의 수는 2명 이상 30명 이하입니다. 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다. 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다. 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다. 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

 

예시

n	lost	reserve	return
5	[2, 4]	[1, 3, 5]	5
5	[2, 4]	[3]	4
3	[3]	[1]	2
7	[2, 3, 4]	[1, 2, 3, 6]	6

 

예제 #1 1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다. 예제 #2 3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

---

2. 문제풀이

하나하나 차근차근 풀어보도록 하겠습니다. 1. 모든 학생들은 1개의 체육복이 있었다.   2. 도둑이 들어 특정학생들의 체육복을 1개씩 훔처갔다.(여러개 있을경우여도 1개만 가져갔으므로)   3. 여분이 있는 학생들은 체육복을 앞뒤 학생들에게 빌려줄수있다.   4. 단 여분을 가져왔는데 자신의 체육복이 사라졌다면 빌려줄 수 없다.   그렇다면 차례대로 만들어 봅시다. 1. 벡터를 총인원수인 N만큼 생성을하고 기본값으로 체육복 1개를 설정합니다.   2. 반복문을 이용하여 체육복을 도난당한 학생들은 체육복을 감소시킵니다.   3. 반복문을 이용하여 여분을 가져온 학생들은 체육복을 추가합니다. 여기까지 했다면 자신이 잃어버리고 가져온 학생들은 체육복이 1이될것입니다. 이제 그러면 2개인 학생들만 신경쓰면 됩니다.   처음부터 순회를 돌기 시작합니다. 4. 자신보다 번호가 큰사람이 체육복이 2개인지 확인하고 체육복이 있다면    빌리는 번호의 체육복 개수를 감소시키고 자신의 체육복 개수를 1개로 증가시킨다.   5. 자기 앞번호가 체육복이 없다면 뒷번호를 확인하고 체육복이 있다면    위와 같이 행동한다.   6. 조건문을 확인할때 번호가 큰사람을 확인할때는 마지막 번호사람은 제외해야한다.    자기보다 큰 번호는 없기 때문이다.    마찬가지로 자기보다 적은번호를 확인할때는 처음 사람은 빌릴 수 없다.    자기보다 적은 번호는 없기 때문이다.   7. 마지막으로 체육복개수가 0이 아닌 개수를 체크하여 반환하면 끝!

---

3. 소스코드

3.1 주석없는 코드

#include <vector>
#include <iostream>
 
using namespace std;
 
int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector<int> check(n, 1);
    for (auto l : lost)        check[l - 1]--;
    for (auto r : reserve)        check[r - 1]++;
    for (size_t i = 0; i < check.size(); i++) {
        if (!check[i]) {
            if (i != check.size() - 1 && check[i + 1] == 2) {
                check[i + 1]--;
                check[i]++;
            }
            else if (i && check[i - 1] == 2) {
                check[i - 1]--;
                check[i]++;
            }
        }
    }
    for (auto a : check)
        if (a != 0)    answer++;
    return answer;
}

3.2 주석있는 코드

#include <vector>
#include <iostream>
 
using namespace std;
 
int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    //총 인원수만큼 벡터를 생성하고 체육복갯수 1로 설정
    vector<int> check(n, 1);
    //체육복을 잃어버린 사람은 1개 마이너스
    for (auto l : lost)        check[l - 1]--;
    //체육복을 여분으로 가져왔다면 1개 플러스
    for (auto r : reserve)        check[r - 1]++;
    //처음부터 돌면서 순회하기
    for (size_t i = 0; i < check.size(); i++) {
        //체육복이 0개라면
        if (!check[i]) {
            //앞의 사람이 여분이 있나 확인하고 있다면 빌리기
            if (i != check.size() - 1 && check[i + 1] == 2) {
                check[i + 1]--;
                check[i]++;
            }
            //뒤에 사람이 여분이 있나 확인하고 있다면 빌리기
            else if (i && check[i - 1] == 2) {
                check[i - 1]--;
                check[i]++;
            }
        }
    }
    //체육복이 몇명이 있나 체크하기
    for (auto a : check)
        if (a != 0)    answer++;
    return answer;
}

3.3 테스트 코드 추가

#include <vector>
#include <iostream>
 
using namespace std;
 
int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    //총 인원수만큼 벡터를 생성하고 체육복갯수 1로 설정
    vector<int> check(n, 1);
    //체육복을 잃어버린 사람은 1개 마이너스
    for (auto l : lost)        check[l - 1]--;
    //체육복을 여분으로 가져왔다면 1개 플러스
    for (auto r : reserve)        check[r - 1]++;
    //처음부터 돌면서 순회하기
    for (size_t i = 0; i < check.size(); i++) {
        //체육복이 0개라면
        if (!check[i]) {
            //앞의 사람이 여분이 있나 확인하고 있다면 빌리기
            if (i != check.size() - 1 && check[i + 1] == 2) {
                check[i + 1]--;
                check[i]++;
            }
            //뒤에 사람이 여분이 있나 확인하고 있다면 빌리기
            else if (i && check[i - 1] == 2) {
                check[i - 1]--;
                check[i]++;
            }
        }
    }
    //체육복이 몇명이 있나 체크하기
    for (auto a : check)
        if (a != 0)    answer++;
    return answer;
}
 
void print(int n, vector<int> lost, vector<int> reserve, int answer) {
    int t = solution(n, lost, reserve);
    if (t == answer)        cout << "정답" << endl;
    else        cout << "틀림" << endl;
}
 
int main() {
    print(5, { 2, 4 }, { 1, 3, 5 }, 5);
    print(5, { 2, 4 }, { 3 }, 4);
    print(3, { 3 }, { 1 }, 2);
    print(7, { 2, 3, 4 }, { 1, 2, 3, 6 }, 6);
    return 0;
}

---

4. 결과