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

학생마다 체육복 보유 상태를 배열로 관리한 뒤, 체육복이 없는 학생에게 앞뒤 학생이 빌려줄 수 있는지 순서대로 확인하는 그리디 문제

 

1. 문제 유형

그리디, 구현, 배열

 

2. 내가 놓친 포인트

처음 떠올린 접근 : 학생 수만큼 배열을 만들고, 체육복이 도난당한 학생은 -1, 여벌이 있는 학생은 +1 해서 상태를 관리하려고 했다.

오답 원인: student 배열 값을 빼고 넣는 과정에서 좀 헷갈려서 값을 잘못 뺏다.

 

3. 핵심 로직 & 해결 방법

핵심 조건: 학생은 자기 번호 기준 앞번호 또는 뒷번호 학생에게만 체육복을 빌릴 수 있다.
여벌이 있는 학생도 도난당했을 수 있고, 최대한 많은 학생이 수업을 들어야 한다.

풀이 아이디어:

1. 학생수만큼 값이 전부 1인 배열 생성한다.
2. lost 학생은 -1 처리, reserve 학생은 +1 처리한다.
3. 체육복이 없는 학생(0)을 만나면 앞/뒤 학생에게 빌릴 수 있는지 확인한다.
4. 마지막에 체육복이 1개 이상 있는 학생 수 반환한다.

4. 구현 코드

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] student = new int[n];
        for(int i = 0; i < n; i++) {
            student[i] = 1;
        }
        
        for (int i = 0; i < lost.length; i++) {
            student[lost[i] - 1]--;
        }

        for (int i = 0; i < reserve.length; i++) {
            student[reserve[i] - 1]++;
        }

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

        return answer;
    }
}

시간 복잡도: O(N) / 공간 복잡도: O(N)

---

 

인사이트

• 정렬이나 복잡한 탐색보다 학생별 상태를 숫자로 관리하는 방식으로 단순화하는 게 핵심.

 

 

문제 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/42862