[프로그래머스] 체육복

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

코딩테스트 연습 - 체육복

---

풀이1.

처음에 문제를 보고 바로 떠오른 방법이다. 그래서 그런지 다소 논리가 깔끔하지는 못한 것 같다...

 

1. hash 맵에 현재 학생들의 체육복 개수 현황을 저장한다.

 

2. 체육복이 없는 학생은 앞뒷번호의 학생이 체육복 여분이 있다면 체육복을 하나 줄 수 있다.

예를 들어 i 번째 학생이 체육복이 없다면 i-1 번째, i+1 번째 학생이 여분이 있다면 i 번째 학생에게 하나를 줄 수 있다.

 

3. i-1 번째 학생이 i 번째 학생에게 체육복을 준 경우와 i+1 번째 학생이 i 번째 학생에게 체육복을 준 두 가지 상황에 대해서 체육복을 1개 이상 가진 학생이 많은 상황을 택하도록 한다.

( 현재 상황에서 최대한 좋은 결과로 보이는 선택을 반복한다. )

 

4. 이때 i-1 번째 학생과 i+1 번째 학생이 동시에 여분을 가지고 있다면, 앞 순서의 학생에게 여분을 받도록 처리한다.

 

[C++]

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int check_max(map<int, int> h_map)
{
    int sum = 0;
    for (auto& ele : h_map)
    {
        if (ele.second > 0)
            sum++;
    }
    return sum;
}

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

    map<int, int> h_map;

    for (int i = 1; i <= n; i++)
    {
        h_map.insert(make_pair(i, 1));
    }

    for (auto& ele : reserve)
    {
        h_map[ele]++;
    }

    for (auto& ele : lost)
    {
        h_map[ele]--;
    }
    
    if (h_map[1] == 0 && h_map[2] == 2)
    {
        h_map[1]++;
        h_map[2]--;
    }
 
    bool flag = false;
    for (int i = 2; i <= n; i++)
    {
        int temp1 = 0; int temp2 = 0;
        if (h_map[i] == 0) // lost
        {
            if (flag==false&&h_map[i - 1] == 2)
            {
                h_map[i - 1]--;
                h_map[i]++;

                temp1 = check_max(h_map);

                h_map[i]--;
                h_map[i - 1]++;

                flag = true;
            }
            if (flag == false&&h_map[i + 1] == 2)
            {
                h_map[i + 1]--;
                h_map[i]++;

                temp2 = check_max(h_map);
                
                h_map[i]--;
                h_map[i + 1]++;

                flag = true;
            }
            if (flag == false&&h_map[i - 1] == 2 && h_map[i+1] == 2)
            {
                h_map[i - 1]--;
                h_map[i]++;

                temp1 = check_max(h_map);

                h_map[i]--;
                h_map[i - 1]++;

                flag = true;
            }
            if (flag == true)
            {
                if (temp1 > temp2)
                {
                    h_map[i - 1]--;
                    h_map[i]++;

                    flag = false;
                    continue;
                }
                else
                {
                    h_map[i + 1]--;
                    h_map[i]++;

                    flag = false;
                    continue;
                }
            }


        }   
    }

    answer = check_max(h_map);

    return answer;
}