[ 프로그래머스 ] 체육복 ( java )

[ 프로그래머스 ] 체육복 ( 자바 )

n명의 학생 중 체육복을 1개 더 있거나(reserve배열) 또는 없는(lost배열)학생이 있다. 

체육복이 없는 학생이 최대한 여벌이 있는 학생한테 빌렸을때 체육복이 있는 학생의 최대값구하기 

단, 학생이 잃어버렸지만 여벌이 있는 경우도 있다. 

 

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

코딩테스트 연습 - 체육복 | 프로그래머스

 

 

구조

cost[i] : i 번 학생이 갖고있는 체육복 수 

cost 1 초기화 

lost 배열 돌며 cost 1 감소 

reserve 배열 돌며 cost 1 증가 

for( 모든 lost학생에 대해 )

    count == 0이면 

        왼쪽 학생 여벌있나?  있으면 빌림 

        오른쪽 학생 여벌있나? 있으면 빌림 

    count에서 0아닌 수 구하기 

 

핵심 

1 체육복 없는 학생이 빌리는 방법 

체육복 없는 학생이 랜덤하게 빌리면 다른 체육복이 없는 학생이 체육복을 빌릴 수 있음에도 빌릴 수 없는 경우가 존재한다. 

아래 그림에서 2번 학생이 1,3번 학생에게 빌릴 수 있는데 3번 학생에게 빌리면 4번학생은 빌릴 수 없다. 

학생	1	2	3	4
체육복 수	2	0	2	0

 

 

따라서, 체육복이 없는 학생들에 대해 순서를 강제함. 

낮은 번호의 체육복없는 학생부터 왼쪽부터 여벌이 있는 학생을 검사한다. 

제일 낮은 번호고 왼쪽부터 검사하므로 오른쪽 옷이 없는 학생이 가능한데도 옷을 못빌리는 경우를 방지할 수 있다. 

 

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요

 

 

코드

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] count = new int[n+1];
        for(int i = 1 ; i <= n ; i++) {
            count[i] = 1;
        }
        
        for(int i = 0 ; i<lost.length ; i++) {
            count[lost[i]] = 0;
        }
        
        for(int i = 0 ; i < reserve.length ; i++) {
            count[reserve[i]]++;
        }
        
        for(int i = 0 ; i < lost.length ; i++) {
            if(count[lost[i]] == 0) {
                if( lost[i] - 1 >= 1 && count[lost[i] - 1] == 2) {
                    count[lost[i]] = 1;
                    count[lost[i] - 1]--;
                }else if(lost[i] + 1 <= n && count[lost[i] + 1] == 2) {
                    count[lost[i]] = 1;
                    count[lost[i] + 1]--;
                }
            }
        }
        
        int ans = 0;
        for(int i = 1 ; i <= n ; i++) {
            if(count[i] != 0)
                ans++;
        }
 
        return ans;
    }
}