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

프로그래머스 programmers Level1 체육복 - java

[문제]

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

프로그래머스

 

[풀이]

level1 수준의 문제가 맞는건지 푸는데 시간이 너무 오래 걸렸다.

처음 문제해결 방안으로 떠오른 방법은 배열의 길이를 이용하면 단순하게 될 것 같았다.
간단히 정리하면 다음과 같다.

1. 여벌의 체육복이 없다고 가정했을때, 현재 가능한 인원수를 산출한다.
   n - lost.length
2. 여벌의 체육복 중 잃어버린 사람이 빌릴 수 있는 수를 산출한다.
   lost[i] == reserve[i-1] || lost[i] == reserve[i+1]
3. 최댓값을 구하여 리턴한다.

위 방법으로 아래의 반례를 고려하지 못했다.

1. 빌릴 수 있는 학생수 (lost 중 reserve±1에 해당하는 원소수) < 여벌의 체육복 수 (reserve)
2. 여벌 체육복을 가진 학생이 도난당하는 경우

반례	n	lost	reserve	return
1.	7	[2, 4, 7]	[1, 3, 5]	6
2.	4	[2, 3]	[3, 4]	3

 

반례를 반영하기위해 가장 중요한 것은, 여벌 체육복을 가진 학생이 도난당하는 경우를 가장 먼저 고려해야 한다.

1. 여벌의 체육복을 가진 학생이 도난 당한 경우, 
   1.1. 해당 학생은 본인의 여별 체육복을 입으면 되므로  lost, reserve  각 배열에서 삭제해줘야 한다.
   1.2. 본인 체육복으로 체육수업에 참여가능하므로 결과값에 학생수를 더해준다.
   ※ 데이터는 int형이므로 본 문제에서 도달할수 없는 임의의 숫자 -9를 설정하여 제거하는 방법을 사용했다.
2. 빌릴 수 있는 학생수를 카운트한다.
   2.1. 체육복이 없는 학생 lost 배열을 for문으로 확인한다.
   2.2. 여벌 체육복  reserve  배열에서 +1 또는 -1 에 해당하는 체육복이 있으면 학생수를 더해준다.
   2.3. 해당 체육복은 대여완료 되었으므로  reserve  배열에서 삭제해준다. (-9 설정)

위 방법은 문제가 없다고 생각했는데, 12번, 18번에서 실패가 발생했다.

검색해본 결과, Arrays.sort() 가 필요하다고 한다.

제한사항 등에서는 제시되어 있지 않아 놓쳤던듯 하다.

 

[java 코드]

private static final int DELETE = -9;

public int solution(int n, int[] lost, int[] reserve) {
    int answer = 0;
    Arrays.sort(lost);
    Arrays.sort(reserve);
    // 여분의 체육이 없을때 현재 가능한 인원 수
    int possibleNum = n - lost.length;
    // 여벌의 체육복을 가진 학생이 도난 당한 경우, 여벌 배열에서 삭제
    int reservableNum = 0;
    for (int i = 0; i < reserve.length; i++) {
        for (int j = 0; j < lost.length; j++) {
            if (reserve[i] == lost[j]) {
                reservableNum++;
                lost[j] = DELETE; // 없애준다.
                reserve[i] = DELETE; // 없애준다.
                break;
            }
        }
    }
    // 빌릴 수 있는 학생 수
    int studentCnt = 0;
    for (int l : lost) {
        for (int i = 0 ; i < reserve.length; i++) {
            if (l - 1 == reserve[i] || l + 1 == reserve[i]) {
                studentCnt++;
                reserve[i] = DELETE;
                break;
            }
        }
    }
    answer = possibleNum + reservableNum + studentCnt;
    return answer;
}

 

[채점 결과]