[Java] 프로그래머스 Level 1 : 체육복

- 문제설명 & 제한사항

- 예시 & 입출력 예

- 해결과정

• 총 3번의 시행착오를 겪었다. 
• 가장 먼저 각 배열을 HashSet으로 만들었다. 문제를 깊게 들어가봤을 때, 배열을 그대로 놓고 푼다면 반복문마다 배열을 계속 뒤지는 상황이 발생할 것이라 판단해서 차라리 처음에 한번 쭉 배열을 돌아, 추후 필요한 값을 찾을 때 시간복잡도가 소요되지 않도록 만들었다.
• 1번 학생부터 n번 학생까지 반복문을 돌며 각 학생이 체육수업에 참여할 수 있는지 판단하고, 참여할 수 있다면 변수 count를 증가시켜주는 방식으로 설계했다.
• 가장 먼저, 반복문을 돌 때 체육복을 잃어버리지 않은 학생을 만나면 count를 증가시켜줬다.
• 두 번째로, 체육복을 잃어버린 학생을 만났다면 다음과 같은 순서대로 체육복을 빌릴 수 있는지 확인했다. [앞번호 학생 --> 본인 --> 뒷번호 학생], 빌릴 수 있다면 count를 증가시켜주고 해당 학생에게 빌려준 여유분은 뒷사람이 중복해서 빌리는 것을 방지하기 위해 삭제한다.
• 앞번호 학생부터 빌리고 이후 순차적으로 본인, 뒷번호 학생으로 나아가는게 가장 최선의 방식이라고 판단했다. --> 그리디(탐욕법)
• 아래는 해당 과정의 소스코드이다

import java.util.Set;
import java.util.HashSet;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int count = 0;
        Set<Integer> set_lost = new HashSet<>();
        Set<Integer> set_reserve = new HashSet<>();
        for(int res : reserve) {
            set_reserve.add(res);
        }
        for(int los : lost) {
            set_lost.add(los);
        }                          // HashSet 각각 선언
        
        for(int i = 1; i <= n; i++) {
            if(!set_lost.contains(i)) count++;
            else if(set_reserve.contains(i - 1)) count++;
            else if(set_reserve.contains(i)) {
                count++;
                set_reserve.remove(i);
            }
            else if(set_reserve.contains(i + 1)) {
                count++;
                set_reserve.remove(i + 1);
            }
        }
        return count;
    }
}

• 이렇게 했을 때 30여개의 테스트 케이스 중 3개를 통과하지 못했다. 
• 본문의 내용 중 체육복을 잃어버린 사람이 여유분을 가지고 있다면 해당 학생은 본인의 체육복을 단 한개만 가지고 있다고 간주한다는 문장을 보고, 첫 번째 코드는 방금 언급한 내용을 위반한다는 사실을 알게되어 메인 for문을 수정했다. 아래는 수정한 내용이다.

for(int i = 1; i <= n; i++) {
	if(set_lost.contains(i) && set_reserve.contains(i)) {
		set_lost.remove(i);
		set_reserve.remove(i);
	} 
	if(!set_lost.contains(i)) count++;
	else if(set_reserve.contains(i - 1)) count++;
	else if(set_reserve.contains(i + 1)) {
		count++;
		set_reserve.remove(i + 1);
	}
}

• 하지만 통과하지 못했던 3개의 테스트 케이스 중 2개는 여전히 만족하지 못했다.
• 이유가 뭘까 고민해보니, 수정한 코드역시 마찬가지로 현재 반복문에서 만나고 있는 학생에 대해서만 체육복을 잃어버리고 동시에 여유분을 가지고 있냐고 판단할 뿐이지 이런 경우, 이전에 앞선 학생이 해당 학생의 체육복을 빌리게 되는 상황을 간과한 것이다.
• 따라서 반복문을 두개로 만들어 미리 (체육복 잃어버림 && 여유분 있음) 의 학생을 찾아서 제거해줬다. 이후 메인 for문을 실행시켜주니 모든 테스트 케이스를 통과할 수 있었다.

- 솔루션

import java.util.Set;
import java.util.HashSet;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int count = 0;
        Set<Integer> set_lost = new HashSet<>();
        Set<Integer> set_reserve = new HashSet<>();
        for(int res : reserve) {
            set_reserve.add(res);
        }
        for(int los : lost) {
            set_lost.add(los);
        }   // HashSet 각각 선언
        for(int i = 1; i <=n; i++) {
            if(set_lost.contains(i) && set_reserve.contains(i)) {
                set_lost.remove(i);
                set_reserve.remove(i);
            } 
        }   // 도둑맞았는데 동시에 여분있는 학생은 타인에게 빌려줄 수 없음
        for(int i = 1; i <= n; i++) {
            if(!set_lost.contains(i)) count++;
            else if(set_reserve.contains(i - 1)) count++;
            else if(set_reserve.contains(i + 1)) {
                count++;
                set_reserve.remove(i + 1);
            }
        }   // 내 앞번호 친구한테 빌리는게 우선. 앞번호 친구가 없으면 뒷번호 친구한테 빌리기
        return count;
    }
}

- 배운점

• 그리디는 현재 상황에서 최선의 해결책을 찾아 나가는 과정이다. 이는 기본적으로 문제를 만났을 때 어떤 방식으로 풀어나갈까 하는 사고력을 요구한다!