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

문제출처

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

코딩테스트 연습 - 체육복

import java.util.Arrays;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length;
        int[] tmp = new int[n + 1];
        Arrays.sort(lost);
        Arrays.sort(reserve);
        for(int r : reserve){
            tmp[r] = 2;
        }  
        for(int l : lost){
            tmp[l]--;
        }

        for(int l : lost){
            if(tmp[l] > 0) {
                answer++;
                continue;
            }
            if(tmp[l - 1] == 2){
                answer += 1;
                tmp[l - 1] = 1;
            }

            else{
                if(l + 1 <= n){
                if(tmp[l + 1] == 2){
                    answer += 1;
                    tmp[l + 1] = 1;
                }
                }
            }

        }
        return answer;
    }
}

테스트케이스 두개때문에 애먹었던 문제

 

우선 여벌의 체육복을 가지고 있는 경우 tmp를 2로 표시해준다.

다음 잃어버린 학생은 tmp에서 -1을 해준다.

그러면 여벌이 있지만 도난당한 학생은 1

그냥 도난당한 학생은 -1이 된다.

잃어버린 학생의 경우 앞 뒤 학생을 확인해 2인경우에 빌리도록한다. 단 1인 경우는 도난 당했지만 이미 체육복이 있는 경우이므로 뒤의 코드를 확인할 필요가 없다.

 

테스트케이스 13,14만 틀렸다고 나와서 반례가 뭘까 한참 생각하다가 결국 검색찬스를 썼다...

정렬이 문제였다.

reserve와 lost가 정렬이 되어있지 않은 경우였던거 같다.

만약 reserve=[2, 4] lost=[3, 1] 같은 경우가 있을때

1번은 2번 체육복을 3번은 4번 체육복을 빌리는게 최대한 많은 체육복을 빌리는 경우가 될 수 있다.

3번 학생은 2번에게도 4번에게도 체육복을 빌릴 수 있다.

하지만 내 코드의 경우 앞의 학생을 먼저 확인하기에 3번은 2번학생의 체육복을 빌려버리게 된다.

그러면 1번 학생은 체육복을 빌릴 수 없다.

아마 13, 14가 이런경우가 아닐까 싶다.