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

프로그래머스 체육복 문제

• 일단 이 문제가 그리디로 분류되었냐면, 순간의 최선이 전체의 최선과 동일하기 때문인데,
• 이 문제를 풀어낸 아이디어를 정리하자면 아래와 같은데
  • 먼저, 학생수만큼 int형 배열을 만들고
  • 학생 번호에 맞는 인덱스 번호를 부여해서
    • 체육복을 도난당한 학생은 -1
    • 여분의 체육복을 가져온 학생은 1
    • 빌리든 뭐든 해서 아무튼 체육복이 구비된 학생 : 0
  • 위 세가지로 모델링했다.
  • 그리고 문제 해결은
    • 체육복을 도난당한 학생은 --1
    • 여분의 체육복을 가져온 학생은 ++1
  • 위 두 과정을 거친다음에
    • 맨 앞에서부터 차례로 체육복이 없을때 앞사람한테 빌릴수 있는지
    • 앞사람에게 빌리는게 불가능하다면 뒷사람에게서 빌릴수 있는지 차례로 탐색
  • 위 두줄의 체육복을 빌리는 과정에서 순간의 최선은 전체의 최선과 동일하기 때문에 그리디로 분류되는것이다.
• 만약다른 규칙이 적용됬다면
  • 일의자리 숫자마다 빌릴수 있는 사람의 규칙이 정해져있다면(예를들어 8인경우 짝수에게만, 5인경우 5의배수에게만, 7인경우 소수인 사람에게만) >> 백준 플레문제 정도 될꺼같고,
  • 친구한테만 빌릴 수 있고, 친구관계가 그래프의 형태로 주어진다면 DFS/BFS문제로 변형 시킬 수도 있다.

아무튼 나의 풀이는 다음과 같다.

import java.util.*;

class Solution {

    public static void main(String[] args) {

        tester(5,new int[] {2,4}, new int[] {1,3,5}, 5);
        tester(5,new int[] {2,4}, new int[] {3}, 4);
        tester(3,new int[] {3}, new int[] {1}, 2);

        return;
    }

    public static void tester(int n, int[] lost, int[] reserve, int answer)  {
        int ret = solution(n,lost,reserve);
        if(ret == answer) {
            System.out.println("OK!!");
        }
        else {
            System.out.printf("No.. ans:%d ,  your return is:%d\n",answer,ret);
        }
        return;
    }


    public static int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        int[] clo = new int[n+1];
        //-1 : 분실
        //0 : 정상
        //1 : 여분 가져옴


        for(int i=0 ; i<lost.length ; i++) {
            clo[lost[i]]--;
        }

        for(int i=0 ; i<reserve.length ; i++) {
            clo[reserve[i]]++;
        }


        //0 번 인덱스
        if(clo[1] == -1 ) {
            if(clo[2] == 1) {
                clo[1] = 0;
                clo[2] = 0;
            }
        }

        //맨처음과 마지막 인덱스 제외는 포문으로 돌리기
        for(int i=2 ; i<=n-1 ; i++) {
            if(clo[i] == -1) {
                if(clo[i - 1] == 1) {
                    clo[i - 1] = 0;
                    clo[i] = 0;
                }
                else if(clo[i + 1] == 1) {
                    clo[i + 1] = 0;
                    clo[i] = 0;
                }
            }
        }
        //마지막 인덱스
        if(clo[n] == -1 ) {
            if(clo[n-1] == 1) {
                clo[n-1] = 0;
                clo[n] = 0;
            }
        }

        int NG = 0;
        for(int i=0 ; i<=n ; i++) {
            if(clo[i] == -1) {
                NG++;
            }
        }



        return n-NG;
    }
}

• 풀이는 코드로 대체한다.