[프로그래머스] 체육복 문제 풀이(탐욕법 Greedy Lv.1) - C++

0. 자세한 설명은 YouTube 영상으로

 

1-1. Set을 활용한 Solution

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        // 1. Set을 만든다
        HashSet<Integer> resList = new HashSet<>();
        HashSet<Integer> losList = new HashSet<>();

        for (int i : reserve)
            resList.add(i);
        for (int i : lost) {
            if (resList.contains(i))
                resList.remove(i);
            else
                losList.add(i);
        }

        // 2. 여분을 기준으로 앞뒤를 확인하여 체육복을 빌려준다.
        for (int i : resList) {
            if (losList.contains(i - 1))
                losList.remove(i - 1);
            else if (losList.contains(i + 1))
                losList.remove(i + 1);
        }
        // 3. 최대한 나눠준 뒤에 lost에 남아있는 학생들은 체육복이 없는 학생들이다.
        return n - losList.size();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] lost = { 2, 4 };
        int[] reserve = { 1, 3, 5 };
        System.out.print(sol.solution(5, lost, reserve));
    }
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1-2. 배열을 활용한 Solution

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        // 1. student 배열 생성
        int[] student = new int[n + 2];
        int answer = 0;

        // 2. reserve / lost 정보 반영
        for (int l : lost)
            student[l]--;
        for (int r : reserve)
            student[r]++;

        // 3. 여분을 기준으로 앞뒤를 확인하여 체육복을 빌려준다.
        for (int i = 1; i <= n; i++) {
            if (student[i] == 1) {
                if (student[i - 1] == -1) {
                    student[i]--;
                    student[i - 1]++;
                } else if (student[i + 1] == -1) {
                    student[i]--;
                    student[i + 1]++;
                }
            }
        }

        // 4. 체육복을 갖고 있는 학생 수를 계산한다.
        for (int i = 1; i <= n; i++)
            if (student[i] > -1)
                answer++;
        return answer;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] lost = { 2, 4 };
        int[] reserve = { 1, 3, 5 };
        System.out.print(sol.solution(5, lost, reserve));
    }
}

• YouTube 영상에 자세한 내용을 정리했으니 참고하세요.