[Java] 프로그래머스 : 체육복(Greedy Algorithm)

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

코딩테스트 연습 - 체육복

 

 

Greedy Algorithm(탐욕 알고리즘)

 : 매 선택에서 현재 당장 최적의 답을 선택(선택했을 경우 다른 가능성을 검증하지 않음)

결과적으로 최고의 선택이지 않을 수 있으나 빠르고 간결한 알고르즘이다.

 

* 동전 문제(최소갯수의 거스름돈 동전을 받아야함) 

1. 1200원을 동전 500원, 100원, 10원으로 나눌땐

 500원 * 2개, 100원 * 2개 로 최적해를 구할 수 있다.

2. 1200원을 동전 500원, 400원, 100원, 10원으로 나눌땐

  500원 * 2개, 100원 * 2개로 받을 시 > 400원 * 3개보다 한개가 많으므로 최적해를 구할 수 없다. 

( 500원이 더 큰 동전이므로 400원 동전보다 500원 동전을 먼저 선택하여 발생하는 문제)

 

 

 

문제

 

 · 전체 학생 : n
 · 도난 당한 학생 번호 : lost
 · 여벌의 체육복 갖고 있는 학생 : reserve
 · 수업을 들을 수 있는 학생 : answer

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
		
        int answer = n - lost.length;
        int count = 0;
        
        // 여벌을 가지고 있던 학생 중 도난을 당했을 경우
        for ( int i=0; i<reserve.length; i++ ){
            for (int j=0; j<lost.length; j++ ){
                if ( reserve[i] == lost[j] ){
                    count++;			// 수업을 들을 수 있는 학생에 count
                    reserve[i] = -1;		// count해준 학생은 비교대상에서 제외하기 위해 -1 설정	
                    lost[j] = -1;		// count해준 학생은 비교대상에서 제외하기 위해 -1 설정
                    break;
                }
            }
        }
        
		// 여벌을 가지고 있던 학생 중 빌려줄 수 있는 학생
        for ( int i=0; i<lost.length; i++ ){
            for (int j=0; j<reserve.length; j++ ){
            
            	// 도난당한 학생 앞뒤 번호 중 여벌을 갖고있는 학생이 있는 확인
                if ( lost[i]+1 == reserve[j] || lost[i]-1 == reserve[j]){	
                    count++;			// 있으면 count
                    reserve[j] = -1;		// count된 학생은 비교대상에서 제외하기 위해 -1 설정
                    break;
                }
                
            }
        }
        
        answer = answer + count;
        return answer;
	}
}