[프로그래머스 Level1][Java] 체육복

 

체육복

※ 그리디 알고리즘(greedy algorithm, 탐욕법)

: 현재의 상황에서 가장 최적의 답을 도출하는 알고리즘 

  가장 이득을 볼 수 있는(탐욕적인) 조건을 유추하여, 최대의 이득을 보기 위해 사용하는 알고리즘

 

※ 생각하기

- 여벌의 체육복을 가진사람은 자신의 번호 앞, 뒤 사람만 체육복을 빌려줄 수 있다.

- 여벌의 체육복을 가져온 학생이 도난당했을 경우, 결국 자신의 체육복만 있으므로 빌려줄 수 없다.

   즉, lost와 reserve에 모두 해당되는 경우! 

 

※ 풀이법

1) 체육활동을 할 수 있는 학생을 파악하기 위해 can 변수를 생성

2) Array.sort()를 통해 lost, reserve 배열을 오름차순으로 정렬

   - 정렬을 하지 않을 경우 테스트 13. 18번에서 에러가 발생한다.

   - 잃어버린 사람의 '앞,뒤' 사람에게 빌려주는 걸로 풀이를 하니깐 초기 입력값 정렬이 필요하다고 한다.

3) '여분의 체육복이 있는 학생이 체육복을 도난 당했을 경우' 로직 구현

   - 즉 lost, reserve 배열에 모두 해당하는 학생이다.

   - 이중 for문을 돌면서 lost[i] = reserve[i]일 경우, 여분의 체육복을 잃어버렸지만 자신이 입을 체육복이 있으므로

     can을 증가시켜주고, lost[i]와 reserve[i]의 값을 -1로 바꿔준다.(여분의 체육복을 빌려줄 수 있는 학생이 없음)

4) '여분의 체육복이 있는 학생이 체육복을 빌려주는 경우' 로직 구현

    - 여분의 체육복이 있는 학생은 자신의 앞, 뒤 번호에 해당되는 학생들만 빌려줄 수 있다.

    - lost[i] + 1 == reserve[j] || lost[i] - 1 == reserve[j] 조건을 만족하면 체육복을 잃어버렸던 학생도 체육활동을

      할 수 있으므로 can을 증가시켜주고 reserve[i]의 값을 -1로 바꾼다.(빌려주면 여분의 체육복은 이제 없음)

5) 리턴해야 될 값(answer)

    - 전체 학생 수 - 체육복을 잃어버린 학생 수 + 체육활동을 할 수 있는 학생 수(여분의 체육복이 있는 학생과 체육복을 빌린 학생)

 

문제는 이해가 됬지만 로직 구현이 어려워 구글링을 통해 분석하고 이해하면서 로직을 구현했다...  ㅠㅠ

    

import java.util.Arrays;

/**
 * 2021-12-05
 * 프로그래머스 level1 : 체육복
 */
public class Solution {
	// 결과 확인을 위함
	public static void main(String[] args) {
		Solution st = new Solution();
		int n = 5;
		int[] lost = {2, 4};
		int[] reserve = {1, 3, 5}; 
		System.out.println(st.solution(n, lost, reserve));
			
		n = 5;
		int[] lost2 = {2, 4};
		int[] reserve2 = {3}; 
		System.out.println(st.solution(n, lost2, reserve2));
		
		n = 7;
		int[] lost3 = {1, 2, 3, 4, 5, 6, 7};
		int[] reserve3 = {1, 2, 3}; 
		System.out.println(st.solution(n, lost3, reserve3));
	}
	
	public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        // 여분의 체육복을 도난당해서 빌려 줄 수 없는 사람 or 체육복을 빌린 사람 = 체육수업이 가능한 사람
        int can = 0;
        
        // 정렬해주지 않으면 테스트 13, 18번이 실패
        Arrays.sort(lost);
        Arrays.sort(reserve);
        
        for(int i=0; i<lost.length; i++) {
        	for(int j=0; j<reserve.length; j++) {
        		// 여분의 체육복이 있지만 도난 당했다면 
        		if(lost[i] == reserve[j]) {
        			// 체육 활동은 가능하므로 can을 1 증가, lost[i]를 -1로 변경
        			can++;
        			lost[i] = -1;
        			// 체육복을 빌려줄 수 없기 때문에 reserve[j]를 -1로 변경
        			reserve[j] = -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]) {
        			// 체육복을 빌렸기 때문에 체육활동을 할 수 있음
        			can++;
        			// 빌려준 사람은 다른 사람에게 또 빌려줄 수 없으므로 -1로 변경
        			reserve[j] = -1;
        			break;
        		}
        	}
        }
        
        answer = n - lost.length + can;
        
        return answer;
    }
}