[programmers] 프로그래머스 체육복(C++)

(주)그렙

[programmers] 프로그래머스 체육복

(C++)

(글쓴날 : 2020.06.06)

 

---

* programmers, 프로그래머스 문제 C++ 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

프로그래머스 체육복

---

1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42862

코딩테스트 연습 - 체육복

---

2) 풀이 과정

* 시간 복잡도 : O(n³)

 

체육복을 도난당한 학생들과, 체육복 여분을 가진 학생들이 주어질 때, 여분을 빌려주어 체육복을 입을 수 있는 총 학생 수를 구하는 문제입니다.

단, 체육복 여분을 가진 학생이 도난을 당했을 시 당연하게도 여분을 빌려주지 못합니다.

 

저의 경우, 그리디를 적용하였고, C++을 사용했습니다.

우선, 체육복을 가진 학생들을 체크하기 위해 bool 배열을 만든 뒤, 도난당한 학생들을 false로 표시하였고, 한 번 더 탐색하여 도난당한 학생들 앞뒤로 여분을 가진 학생이 있는지 확인하여 체육복을 입을 수 있는 총 학생 수를 구했습니다.

---

3) 코드

 

* C++ 코드

#include <string>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
 
bool stu[31];
 
int solution(int n, vector<int> lost, vector<int> reserve)
{
    int answer = 0;
 
    memset(stu, true, sizeof(stu));
 
    for (int i = 0; i < lost.size(); i++)
    {
        stu[lost[i]] = false;
        for (int j = 0; j < reserve.size(); j++)
        {
            if (lost[i] == reserve[j])
            {
                stu[lost[i]] = true;
                reserve.erase(reserve.begin() + j);
            }
        }
    }
 
    for (int i = 1; i < n + 1; i++)
    {
        if (!stu[i])
        {
            bool check = false;
            for (int j = 0; j < reserve.size(); j++)
            {
                if (i - 1 == reserve[j])
                {
                    reserve.erase(reserve.begin() + j);
                    check = true;
                    break;
                }
            }
 
            if (!check)
            {
                for (int j = 0; j < reserve.size(); j++)
                {
                    if (i + 1 == reserve[j])
                    {
                        reserve.erase(reserve.begin() + j);
                        check = true;
                        break;
                    }
                }
            }
 
            if (check)
            {
                answer++;
                continue;
            }
 
            continue;
        }
        answer++;
    }
 
    return answer;
}

---