[프로그래머스]탐욕법(Greedy) : 체육복 (level 1) (java, c++)

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

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

 

 

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        
        // '여분'의 체육복 개수 배열. 하나도 없으면 -1
        int[] arrOk = new int[n + 1];
        
        // 여분의 체육복 배열 반영
        for (int i = 0; i < reserve.length; i++) {
            arrOk[reserve[i]]++;
        }
        // 부족한 체육복 배열 반영 (도난당한 학생 반영)
        for (int i = 0; i < lost.length; i++) {
            arrOk[lost[i]]--;
        }
 
        for (int i = 0; i < lost.length; i++) {
            
            int now = lost[i];
            // 도난당한 학생 건너뛰기
            if (arrOk[now] >= 0) {
                continue;
            }
 
            // 앞번호 학생 -> 뒷번호 학생 순으로 여분 여부 검사
            if (now - 1 >= 1 && arrOk[now - 1] > 0) {
                arrOk[now - 1]--;
                arrOk[now]++;
                continue;
            }
            if (now + 1 <= n && arrOk[now + 1] > 0) {
                arrOk[now + 1]--;
                arrOk[now]++;
            }
 
        }
         
        // '여분'이 0개 이상인 사람 수 구하기
        int answer = 0;
        for (int i = 1; i < arrOk.length; i++) {
            if (arrOk[i] >= 0) {
                answer++;
            }
        }
        return answer;
    }
}

 

c++소스

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {

    // 학생 별 옷 개수
    vector<int> cloth(n + 2);
    for (int i = 0; i < lost.size(); ++i)
    {
        --cloth[lost[i]];
    }
    for (int i = 0; i < reserve.size(); ++i)
    {
        ++cloth[reserve[i]];
    }

    for (int i = 1; i <= n; ++i)
    {
        // 여분의 체육복이 있으면
        if (cloth[i] > 0)
        {
            // 여분 체육복 있는 학생의 앞 또는 뒤에 체육복 잃어버린 학생이 있으면
            if (cloth[i - 1] < 0)
            {
                cloth[i] = cloth[i - 1] = 0;
            }
            else if (cloth[i + 1] < 0)
            {
                cloth[i] = cloth[i + 1] = 0;
            }
        }
    }

    // 옷이 부족하지 않은 학생수
    int answer = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (cloth[i] >= 0)
        {
            ++answer;
        }
    }
    return answer;
}

 

그리디 알고리즘

: 최적해를 구하는 데에 사용되는 근사적인 방법으로,

여러 경우 중 하나를 결정해야 할 때마다

그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여

최종적인 해답에 도달한다

(내가 문제를 풀이한 방식이 '그리디'적인지는 아직 잘 모르겠다.)

 

 

i 번째 학생을 D[ i ] 라 하면,

체육복을 가져 오지 않은 D[ i ] 는

앞, 자기자신, 뒤 학생 을 검사할 수 있다. 

 

 

여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

문제에 따르면 가장 우선순위 검사대상은 자기자신이다. 

 

즉 검사의 우선순위는

1. D[ i ]

2. D[i - 1]

3. D[i + 1]

이다. (2번과 3번은 바뀌어도 상관없다. 방향만 일정하면 된다)

 

 

이때, 욕심을 부려서 한가지 반복문에 모든 작업을 하려고 했다가 애를 먹었다.

욕심부리지 말고, 작업을 분할해서 순차적으로 나눠해주자 

분명 욕심 문제였는데 음...