체육복-알고리즘(Programmers)

문제

예전에도 이 문제를 몇번 풀어본적이 있는데 그때는 잘 해결하지 못해서 답을 보고는 했다.
이제는 그래도 문제를 풀면서 어떻게 구현해야할지 생각하고 연습하다보니 방법을 찾을 수 있었다.

접근법

우선 사람(n+1)에 인원수만큼의 배열을 만들었는데( 사실 이건 굳이 필요하지 않았던 것 같다. 어차피 체육복 배열의 인덱스 번호가 사람을 나타내면 되기 때문 )

1차 접근

체육복의 배열(n+1)을 만듬 (인덱스0은 무시)
그리고 lost면 cnt를 0으로 세팅하고 reserver면 한개를 나눠줄 수 있기 때문에 2로 세팅하였다.

하지만 여기서 문제에서의 한가지 중요한 조건을 제대로 확인하지 않았다.

여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다.
이때 이 학생은 체육복을 하나만 도난당했다고 가정하며,
남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

즉 0 과 2로 세팅을 하기보다는 +1과 -1로 각 상태에 증감으로 세팅하는게 맞다고 본다.

그런 후에 각 조건에 따라 앞의 번호가 체육복이 없으면 뒤에서 나눠주고 뒤의 번호가 없으면 앞에서 나눠주고 각 상황에 대한 분기를 진행하면 된다.

내 코드

public static int solution(int n, int[] lost, int[] reverse){
        int answer = 0;

        int student[] = new int[n+1]; //학생배열
        int clothes[] = new int[n+1]; //옷배열

        for(int i=1; i<=n; i++){
            student[i] = i;
        }
        clothes[0] = -1;            //0인덱스는 안쓰는 인덱스
        for(int i=1; i<clothes.length; i++){
            clothes[i] = 1;
        }

        for(int i=0; i<lost.length; i++){
            int index = lost[i];
            clothes[index] -= 1;
        }

        for(int i=0; i<reverse.length; i++){
            int index = reverse[i];
            clothes[index] += 1;
        }


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

   
        answer = (int)Arrays.stream(clothes).filter(x->x>=1).count();

        return answer;
    }

다른사람의 코드를 보니 이렇게도 더 쉽게 풀 수 있구나라는 걸 깨달았다.

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] people = new int[n];
        int answer = n;

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

        for (int i = 0; i < people.length; i++) {
            if(people[i] == -1) {
                if(i-1>=0 && people[i-1] == 1) {
                    people[i]++;
                    people[i-1]--;
                }else if(i+1< people.length && people[i+1] == 1) {
                    people[i]++;
                    people[i+1]--;
                }else 
                    answer--;
            }
        }
        return answer;
    }
}