[JAVA] 프로그래머스 - 체육복

문제 내용

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

코딩테스트 연습 - 체육복

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

---

문제 접근 방법

단순하게 체육복 2벌 갖고온 학생이 안갖고온 학생한테 한벌씩 최대한 많이 나눠주면 되는 문제이다.

주의해야할 점은 2벌 갖고온 학생이 1벌을 도둑맞았다면 이 학생의 체육복은 1벌이 남기때문에 다른 학생을 빌려 줄 수 없다는 점을 고려하면 된다.

 

따라서 문제는 큰틀로 나누면 아래와 같은 두가지 과정을 생각하여 코드를 작성 하면된다.

1. 여벌의 체육복을 갖고온 학생이 도난당했을때

2. 여벌의 체육복을 갖고온 학생이 도난 안당했을때

 

본인의 풀이 방법을 설명하자면

1. 체육복을 빌려주는 조건중 앞뒤 학생중 한명에게만 빌려줄 수 있기때문에 번호 순서대로 탐색하며 빌려줄수 있는지 없는지 확인하기 위해선 입력 받은 lost 배열과 reserve 배열을 정렬해줘야 한다.
2. lost 학생이 체육복을 빌렸을때를 나타낼 boolean[] checkL (빌렸다면 checkL=true;)
   reserve 학생이 체육복을 빌려줬을때를 나타낼 boolean[] checkR (빌려줬다면 checkR=true;) 을 정의한다.
3. 다만 체육복을 빌려주기전에 여벌을 갖고온 학생이 도둑맞았는지 먼저 탐색해준다.
   이 학생이 도둑 맞았다면 이 학생에 해당하는 인덱스 번호를 갖고 checkL, checkR에 true 처리를 한다.
4. 위과정을 2중 for문을 통해 다 탐색하고 나오면 answer = 전체학생 - checkL이 false 인 학생이 답이된다.
   checkL == false 인 학생은 체육복을 빌리지 못했기에 수업에 참여할 수 없다.

 

위와같은 과정을 통해 문제를 풀었고 자세한 설명은

풀이의 주석에 달아놨다.

 

---

풀이

import java.util.Arrays;

public class Solution {
	static boolean[] checkR;//빌려주는 학생이 빌려줬는지 아닌지 체크
	static boolean[] checkL;//빌리는 학생이 빌렸는지 아닌지 체크
	public static int solution(int n, int[] lost, int[] reserve) {
		int answer = 0;
		int other = 0;
		checkR = new boolean[reserve.length];
		checkL = new boolean[lost.length];
		
		//오름차순 정렬
		Arrays.sort(lost);
		Arrays.sort(reserve);
		
		//여벌체육복 갖고온 학생이 도난 당했을때
		for(int i=0; i<reserve.length; i++) {
			if(checkR[i]) {continue;}//이미 빌려줬다면 continue
			for(int j=0; j<lost.length; j++) {
				if(checkL[j]) {continue;}//이미 빌렸다면 continue
				if(reserve[i]==lost[j]) {//여벌체육복 갖고온 본인이 도난당했을때.
					checkR[i]=true;//본인 true
					checkL[j]=true;//본인 true
					break;
				}
			}
		}
		
		//여벌체육복 갖고온 학생이 도난 안당했을때
		for(int i=0; i<reserve.length; i++) {
			if(checkR[i]) {continue;}//이미 빌려줬거나 못빌려주면 continue
			for(int j=0; j<lost.length; j++) {
				if(checkL[j]) {continue;}//이미 빌렸거나 본인체육복을 쓴다면 continue
				//앞뒤 학생 중 한명에게 빌려줄수 있을경우
				if(reserve[i]+1==lost[j]||reserve[i]-1==lost[j]) {
					checkR[i]=true;//빌려줬기 때문에 true
					checkL[j]=true;//빌렸기 때문에 true
					break;
				}
			}
		}
		for(boolean c:checkL) {
			if(!c) {other++;}//못빌린 학생 카운트
		}
		answer = n-other; //수업들을 수 있는 전체 학생 = 전체학생 - 못빌린 학생 
		return answer;
	}
}

---

마치며

음.. 크게 설명할부분은 없다고 생각하고 정렬해야하는 점과 도난당한 학생이 여벌의 체육복을 갖고온 경우인지 아닌지만 생각하면 되는 문제라고 생각한다.