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

문제

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

코딩테스트 연습 - 체육복

풀이

문제 태그 자체는 그리디 문제인데 필자는 조건을 많이 쳐서 구현식으로 문제를 풀었다.

일단 전체 체육복의 갯수를 관리하는 num이라는 테이블을 만들어주었고, lost에 대해선 -1, reserve에 대해선 +1을 해주어 초기값 세팅을 하였다. 이후에는 체육복의 테이블에 대해 for문을 돌아서 크게 3가지 분기로 나누어주었는데

i) i가 첫번째 사람일때 - 첫번째 사람은 뒷 사람에게 체육복을 빌려주거나 받을 수 없으므로 자신의 체육복이 2개이고, 앞 사람의 체육복의 개수가 0개이면 빌려줄 수 있도록 하였다.

ii) i가 마지막 사람일때 - 마지막 사람은 앞 사람에게 체육복을 빌려주거나 받을 수 없으므로 자신의 체육복이 2개이면 뒷 사람에게 나누어주거나, 뒷 사람의 체육복이 2개이면 받는 식으로 구현하였다.

iii) i가 첫번째, 마지막번째 사람이 아닐때 - 이때는 3개의 조건으로 또 갈리는데 일단 자신의 체육복이 2개인 조건으로 또 좁혀서 뒷 사람의 체육복이 없고, 앞 사람은 체육복이 있을 때 뒷 사람에게 우선순위로 빌려주었다.

뒷 사람, 앞사람 모두 체육복이 없을 때 또한 뒷 사람에게 우선순위로 빌려줄 수 있도록 하였다. 이렇게 구현한 이유는 앞 사람은 당장의 체육복이 없더라도 for문을 돌다보면 다른 사람에게 받을 가능성이라도 있지만 뒷 사람 같은 경우는 이번 턴을 지나면 받을 가능성이 아예 없어지기 때문에 뒷 사람에게 우선순위를 부여해주었다.

뒷 사람은 체육복이 있지만 앞 사람은 체육복이 있을 때에는 앞 사람에게 체육복을 빌려줄 수 있도록 하였다.

이러한 조건을 쳐서 for문을 모두 돌게하고, 이후에 체육복 테이블의 값이 0이 아닌 곳의 개수를 답으로 리턴해주면 정답을 얻을 수 있다.

 

코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;

    vector<int> num(n);

    for (int i = 0; i < n; i++)
    {
        num[i] = 1;
    }

    for (int i = 0; i < lost.size(); i++)
    {
        num[lost[i] - 1]--;
    }
    for (int i = 0; i < reserve.size(); i++)
    {
        num[reserve[i] - 1]++;
    }

    for (int i = 0; i < n; i++)
    {
        if (i == 0)
        {
            if (num[i + 1] == 0 && num[i] == 2)
            {
                num[i]--;
                num[i + 1]++;
            }
        }
        else if(i == n - 1)
        {
            if (num[i] == 0 && num[i - 1] == 2)
            {
                num[i]++;
                num[i - 1]--;
            }
            if (num[i] == 2 && num[i - 1] == 0)
            {
                num[i]--;
                num[i - 1]++;
            }
        }
        else
        {
            if (num[i] == 2)
            {
                if (num[i - 1] == 0 && num[i + 1] != 0)
                {
                    num[i]--;
                    num[i - 1]++;
                }
                else if (num[i - 1] == 0 && num[i + 1] == 0)
                {
                    num[i]--;
                    num[i - 1]++;
                }
                else if (num[i - 1] != 0 && num[i + 1] == 0)
                {
                    num[i]--;
                    num[i + 1]++;
                }
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (num[i] != 0)
        {
            answer++;
        }
    }

    return answer;
}