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

사진을 클릭하면 해당 문제로 이동

💡풀이

import java.util.Arrays;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] students = new int[n + 1];
        Arrays.fill(students, 1);
        students[0] = -1;

        for(int number : reserve) {
            students[number]++;
        }

        for(int number : lost) {
            students[number]--;
        }

        for(int number = 1; number < n + 1; number++) {
            if(students[number] == 0) {
                if(students[number - 1] > 1) {
                    students[number - 1]--;
                    students[number]++;
                } else if(number < n && students[number + 1] > 1) {
                    students[number + 1]--;
                    students[number]++;
                }
            }
        }
        return (int) Arrays.stream(students).filter(e -> e > 0).count();
    }
}

---

📖문제 복기

실패했던 이유 요약

처음에는

for(int number : lost)

해당 반복문을 돌렸더니 일부 테스트 케이스에서 실패했고,

for(int number = 1; number < n + 1; number++)

 

해당 반복문으로 변경하니 통과할 수 있었다.

실패 원인: 탐색 순서의 불확실성

for (int number : lost) 방식은 lost 배열에 담긴 임의의 순서대로 체육복이 없는 학생을 확인하게 된다.

이 경우, 최적의 선택이 아닌 상황이 발생할 수 있다. 예를 들어 4번 학생이 3번 학생에게 먼저 빌려버리면, 정작 3번 학생에게 빌려야만 했던 2번 학생이 기회를 놓치는 상황이 생길 수 있기 때문이다.

만약 lost 배열을 쓰고 싶다면, Arrays.sort(lost)로 정렬한 뒤 사용하면 통과할 수 있다

 

💡일관된 순서로 탐색

학생 번호 1번부터 순서대로 문제를 해결하는 for (int number = 1; number < n + 1; number++) 방식처럼

일관된 순서(항상 앞 번호 학생부터)로 탐욕적인(Greedy) 선택을 하면, 특정 선택이 다른 학생의 기회를 뺏는 경우를 방지하고 항상 최적의 결과를 보장할 수 있습니다.

---

GitHub - okjunghyeon/Programmers_CodingTest: 프로그래머스 관련 코딩테스트 문제를 풀이한 저장소입니다.