[그리디] 문제 이름 : 체육복

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

 

1. 사용 알고리즘

그리디

 

2. 문제 해결 아이디어 

체육복을 가진 학생의 수가 최대가 되기 위해서는 체육복을 도난 당한 학생의 앞뒤 학생이 여별 체육복이 있을 때 앞의 학생의 여벌 체육복을 빌리도록 해야한다. 

 

3. 코드

구현방식)

1. lost[]와 reserve[]를 전체 학생의 배열 stu[]에 적용시켜 하나의 배열로 합쳐서 처리하도록 함 --> lost[]와 reserve[] 각각을 탐색하지 않아도 됨, 여벌 체육복을 가져온 학생이 도난당한 경우에 대해서도 한번에 처리 가능함

2.  반환 값 answer(체육 수업을 들을 수 있는 학생 수)를 전체 학생 수의 값 n으로 초기 설정함 --> 0으로 초기화해서 증가시키는 것보다 감소시키는 경우가 코드가 더 간결함

//조건 : 주어진 배열들이 정렬되어 있지 않다

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        //lost: 잃어버린 학생 번호 배열, reserve: 여벌 옷 가지고 있는 학생 번호 배열 
        
        //lost와 reserve를 합쳐서 하나의 배열로 생각하기!
        int stu[] = new int[n];
        int answer = n; //전체 학생 수로 설정해두고 감소시키기 -> 증가시키는 경우보다 코드가 적어짐 
        
        for(int i : lost)
            stu[i-1]--;
        for(int j : reserve)
            stu[j-1]++;
            
        //그리디 문제인 이유 : 앞뒤 사람 모두 여유복을 가지고 있을 때, 앞 사람의 것을 빌려야 최대가 나옴
        for(int k = 0; k < stu.length; k++){
            if(stu[k] == -1){ //체육복을 도난당한 학생의 경우
                if(k-1 >= 0 && stu[k-1] == 1){ //앞 사람 먼저 확인  
                    stu[k]++;
                    stu[k-1]--;
                }
                else if(k+1 < stu.length && stu[k+1] == 1){
                    stu[k]++;
                    stu[k+1]--;
                }
                else answer--; //체육수업을 듣지 못하는 학생 
            }
        }
        return answer;
    }
}

 

추가 개념 정리)

*자바의 for문에서 for(:) 의 기능

for(Object:List) -> List에서 차례대로 원소를 꺼내서 Object에 저장을 하겠다는 의미

class Main{
	public static void main(String args[]){
    	int num[] = {1,2,3};
        
        for(int i : num)
        	System.out.println(i);
            
        //이 코드랑 동일한 의미!
        for(int i = 0; i < num.length; i++)
        	System.out.println(num[i]);
    }
}

/* 
출력 결과 
1
2
3
*/