프로그래머스 - 체육복 java :: 탐욕법(Greedy) :: 42862

문제 링크

코딩테스트 연습 - 체육복 | 프로그래머스 스쿨 (programmers.co.kr)

---

문제 풀이

보통 이런 문제들을 보면 정답의 기준에서 찾는 것보다 정답이 아닌 것을 기준으로 보고 푸는 게 효율이 좋더라구요.

모두가 체육복을 가지고 있다고 가정하고, 없는 사람을 제거하는 방식으로 풀었습니다.

public int solution(int n, int[] lost, int[] reserve) {
    int[] haves = new int[n+2]; // 0번째 인덱스와, 마지막 인덱스는 비워두는 용도
    int answer = n;

    for(int l : lost) haves[l]--;
    for(int r : reserve) haves[r]++;

    for(int i=1; i<=n; i++) {
        if(haves[i] == -1) {
            if(haves[i-1] > 0) {
                haves[i]++;
                haves[i-1]--;
            } else if(haves[i+1] > 0) {
                haves[i]++;
                haves[i+1]--;
            } else {
                answer--;
            }
        }
    }

    return answer;
}

• int[] haves

배열의 크기를 [n+2]로 만든 이유는 lost와 reverse에 담긴 요소들이 1번부터 시작하기 때문인 것도 있고

아래 반복문의 조건에서 i-1 또는 i+1 해야 하는 부분에서 배열의 크기를 넘어갈 가능성이 있기 때문입니다.

물론 조건처리 하면 되기는 하지만, 그러면 또 조건 2개(i-1 >= 0, i+1 < haves.length-1)를 추가해야 하기 때문에 편의를 위해 [n+2]로 만들어 0번째 인덱스와 마지막 인덱스는 사용하지 않습니다.

그리고 어차피 int 배열이라 0으로 초기화되기 때문에 반복문의 조건문을 통과할 일도 없습니다.

순서대로 탐색하며 나(i)를 기준으로 왼쪽부터 빌리고, 없으면 오른쪽 빌리고, 내 양쪽이 모두 없으면 체육복이 없는 겁니다.

테스트 케이스 처리속도

• 🔥 0.01 ~ 0.02ms

---