[Java] 체육복

문제

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

코딩테스트 연습 - 체육복

 

 

풀이

오랫동안 헤맸던 문제... ㅠㅠ

 

내가 진행했던 테스트케이스는 아래 7가지이다.

n(int)	lost(int[])	reserve(int[])	Return
5	[2, 4]	[1, 3, 5]	5
5	[2, 4]	[3]	4
3	[2]	[2]	3
5	[3]	[2, 3]	5
5	[3]	[3, 4]	5
7	[1, 5, 6, 7]	[4, 6]	5
5	[3, 5]	[2, 4]	5

1, 2번째 줄 :

   기존 test case

3, 4, 5, 6번째 줄 :

   체육복을 잃어버린 학생과 여벌을 가져온 학생이 같은 test cases

7번째 줄 :

   여벌의 체육복이 있지만 앞 뒤로 체육복이 없는 학생이 있는 test case

 

이 때 주의해야 할 것은 체육복은 무조건 앞, 뒤 번호에게만 전달 가능하다는 것이다.

예를 들어,

2번에게 2개, 3번에게 1개, 4번에게 0개가 있을 경우 

2번이 3번에게 한개를 전달하고, 3번이 4번에게 전달하는 방식은 불가능하다.

 

 

다음은 코드에 대한 설명이다.

 

1. flags는 각 학생의 체육복 개수를 담는 int형 배열이다.

n이나 lost, reserve 배열에서 번호가 1부터 시작하므로

배열의 길이도 n+1로 설정했다.

(인덱스 0~n이 아닌 1~n+1에 저장하기 위함)

 

2. //초기화

각 학생에게 체육복을 한 벌씩 할당했다.

 

3. // lost와 reserve가 같을 때

위 테스트 케이스들을 통해 lost와 reserve가 같을 경우,

다른 학생에게 체육복을 받지도, 주지도 못한다.

따라서 아예 -1로 설정했다. ( 왜 -1인지는 5번에 나옴)

 

4. // 빼기

lost에 해당하는 학생들에게 -1씩 해준다.

 

5. // 나눠주기

5-1. reserve에 해당하는 여분의 체육복이 있는 학생들에게 +1씩 해준다.

 

5-2.

reserve[i]번 학생의 체육복 개수가 2개 이상

AND reserve[i]번 학생 앞 번호의 학생이 존재

AND 앞 번호 학생의 체육복 개수가 0개

 

5-3.

reserve[i]번 학생의 체육복 개수가 2개 이상

AND reserve[i]번 학생 다음 번호의 학생이 존재

AND 뒷 번호 학생의 체육복 개수가 0개

 

→ 앞의 2(// lost와 reserve가 같을 때)에서 체육복 개수를 -1로 설정한 이유이다.

   0 이상의 개수로 설정한다면 위 조건문에 해당하게 될 수 있어 음수인 -1로 설정했다.

 

6. 체육복 개수가 1개 이상인 학생 수를 answer에 저장 

 

 

코드

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        int[] flags = new int[n+1]; //0~n
        
        //초기화
        for(int i=1; i<=n; i++)
            flags[i] = 1;
        
        //lost와 reserve가 같을 때
        for(int i=0; i<lost.length; i++){
            for(int j=0; j<reserve.length; j++){
                if(lost[i]==reserve[j]){
                    flags[lost[i]] = -1;
                    answer++;
                    break;
                }                    
            }
        }
        
        //빼기
        for(int i=0; i<lost.length; i++)
            flags[lost[i]] -= 1;
        
        //나눠주기
        for(int i=0; i<reserve.length; i++){    
            flags[reserve[i]] += 1;
            
            if(flags[reserve[i]]>1 && reserve[i]-1>0 && flags[reserve[i]-1] == 0){
                flags[reserve[i]-1] += 1;
                flags[reserve[i]] -= 1;
            }else if(flags[reserve[i]]>1 && reserve[i]+1<n+1 && flags[reserve[i]+1] == 0){
                flags[reserve[i]+1] += 1;
                flags[reserve[i]] -= 1;
            }
        }

        for(int i=1; i<n+1; i++){
            System.out.print(flags[i]+" ");
            if(flags[i]>0)
                answer++;
        }    
        
        return answer;
    }
}