프로그래머스 - 체육복

카테고리: 그리디

레벨: 1

언어: Java

 

문제

---

처음에 문제를 이해하는데 어려움은 없었다. 만약에 2번 학생이 체육복이 없다면 3번이나 1번 학생이 체육복을 빌려주면 되고, 체육복이 없는 사람을 기준으로 -1이나 +1을 해줘서 풀면 된다고 생각했다.

하지만 막상 풀어보니 코드를 실행했을 때는 테스트 케이스가 맞았지만, 제출을 해보니 중간에 실패가 몇 개 발생하였다.

어떤 것이 문제인지 살펴보니 체육복을 도난당한 학생들과 여벌의 체육복이 있는 학생들을 정렬시켜 줘야지 번호가 섞여도 문제가 되지 않았고, 여벌의 체육복을 가져온 학생도 도난당할 수 있다는 제한 사항도 있어서 처리가 필요했었다.

 

입출력 예시

---

 

풀이

---

public int solution(int n, int[] lost, int[] reserve) {

    int count = n - lost.length;

    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]) {
                count++;
                lost[i] = -1;
                reserve[j] = -1;
                break;
            }
        }
    }

    for (int i = 0; i < lost.length; i++) {
        for (int j = 0; j < reserve.length; j++) {
            if (lost[i] == reserve[j] - 1 || lost[i] == reserve[j] + 1) {
                count++;
                lost[i] = -1;
                reserve[j] = -1;
                break;
            }
        }
    }

    return count;
}

체육복 문제는 그리디 카테고리에 있는 문제이다.

 

int count = n - lost.length;

Arrays.sort(lost);
Arrays.sort(reserve);

먼저 전체 횟수를 저장할 count 변수를 생성하고 전체 학생 수에서 체육복을 도난 당한 학생의 수만큼 빼서 저장했다.

그런 다음 도난 당한 학생들의 번호가 담긴 lost 배열과 여벌의 체육복을 가지고 있는 reserve 배열을 Arrays 클래스의 sort 메서드를 사용하여 정렬해 줬다.

 

for (int i = 0; i < lost.length; i++) {
    for (int j = 0; j < reserve.length; j++) {
        if (lost[i] == reserve[j]) {
            count++;
            lost[i] = -1;
            reserve[j] = -1;
            break;
        }
    }
}

정렬이 완료되면 이제 반복문을 돌면서 체육복을 빌려줘야 되는데 그러기에 앞서 여벌의 체육복을 가지고 있는 학생도 도난당할 수 있기 때문에 반복문을 통해서 도난당한 학생의 번호와 여벌의 체육복을 가지고 있는 학생의 번호가 같다면 각 배열의 i와 j번째 값을 -1로 저장해 주고 count 값을 증가시켜 준다.

 

for (int i = 0; i < lost.length; i++) {
    for (int j = 0; j < reserve.length; j++) {
        if (lost[i] == reserve[j] - 1 || lost[i] == reserve[j] + 1) {
            count++;
            lost[i] = -1;
            reserve[j] = -1;
            break;
        }
    }
}

다음 반복문으로는 도난당한 학생의 번호 앞, 뒤로 여벌의 체육복을 가지고 있는 학생들을 확인하여 빌려주는 코드를 작성하였다.

여벌의 체육복을 가진 학생이 있는지 도난 당한 학생 번호를 기준으로 -1, +1을 하여 체크하고 만약에 있다면 빌려주게 된다.

도난 당한 학생이 체육복을 빌렸다면 체육 수업을 들을 수 있게 돼서 count를 증가시켜 주고 lost와 reserve의 i, j번째 위치 값을 -1로 저장해 준다.

 

문제를 풀어보면서 크게 어렵다고 느껴지진 않았지만, 예외 사항을 고려하지 못했던 것 같았다. 너무 입출력 예시만 확인하다 보니 번호가 섞이는 경우를 생각하지 못했고 왜 실패했는지 이해하는데 시간이 오래 걸렸다.

그리디는 항상 최선의 결과를 주지 않는다고 배웠는데 문제를 풀어보며 확실히 알 수 있었다. 정렬되지 않은 데이터를 그리디로 풀어보니 항상 테스트가 성공하지 않는다는 것을 알게 되었다.