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

체육복(Level1)

문제

전체문제 보기

코딩테스트 연습 - 체육복

접근법

이 문제는 Level1 문제 답게 복잡하게 생각한다거나, 특별한 반례를 고민해야하는 문제는 아니다. 아래와 같이 간단하게 해결 할 수 있다. 실제 코딩테스트에서 이런 문제가 나온다면 빠른 시간에 풀수 있어야 하기 때문에 빠르게 문제를 해석하고 구현하는 연습을 하자.

• 모든 학생들에 대한 벡터를 만들고 체육복에 대한 정보를 입력한다.
• 모든 학생에 대해서 조회를한다. 만약 체육복을 2벌 가지고 있는 학생이 있다면,
  • 앞에 있는 학생의 체육복이 0개라면 앞에 학생에게 체육복을 하나 빌려준다.
  • 앞에 있는 학생의 체육복이 0개가 아니고, 뒤에 있는 학생의 체육복이 0개라면 뒤에 있는 학생에게 체육복을 하나 빌려준다.
• 최종 체육복을 하나 가지고 있는 학생을 카운트 한다.

이 문제에서 주의해야 할 점은 체육복정보를 입력할때 아래와 같은 조건이다.
"여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다."
때문에 체육복에 대한 정보를 입력할 때 다음과 같이 한다면 오답이 발생하니 주의하자.

    vector<int> student(n + 2, 1);
    for(int i : lost)
        student[i] = 0;

    for(int i : reserve)
        student[i] 2;

대신 전체 여벌 옷을 가져오면 1증감, 도난을 당하면 1감소를 하여 위 문제의 조건을 충족시켜 주자.

    vector<int> student(n + 2, 1);
    for(int i : lost)
        student[i]--;
    for(int i : reserve)
        student[i]++;

전체 구현

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    // 전체 반복문에서 배열의 마지막 값 접근시 발생할 수 있는 예외를 줄이기 위해서 n+2개의 원소를 선언함.
    // 기본 1벌씩 가지고 있는 것으로 초기화
    vector<int> student(n + 2, 1);

    // 체육복 도난, 여벌 정보를 입력
    for(int i : lost)
        student[i]--;

    for(int i : reserve)
        student[i]++;

    // 체육복을 빌려주는 알고리즘
    for(int i = 1; i < n + 1; i++)
        if(student[i] == 2)
            if(student[i - 1] == 0)
            {
                student[i - 1]++;
                student[i]--;
            }
            else if(student[i + 1] == 0)
            {
                student[i + 1]++;
                student[i]--;
            }

    // 체육복을 하나 이상 가지고 있는 학생들 조회
    for(int i = 1; i < n + 1; i++)
        if(student[i] >= 1)
            answer++;

    return answer;
}