[프로그래머스 / 체육복 / JAVA / 탐욕법]

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

프로그래머스

 

문제 접근

학생들의 체육복 소유 여부를 확인하는 boolean 배열과 체육복 여벌을 갖는 boolean 배열을 기본적으로 사용해서 문제를 풀었다.

0번 인덱스로 시작하면 헷갈릴 거 같아서 크기가 1 더 큰 배열로 만들어주었음

두 배열 다 체육복을 갖고있으면 true, 없으면 false

체육복을 갖고 있는지 검사로 다 확인 후에

2번 부터 끝 번호 앞 까지 양 옆 친구들의 체육복 소유 여부, 자신의 여벌 체육복 여부를 확인 후 왼쪽 친구 먼저 주도록 하였음

* 첫 번호와 끝 번호는 양 옆 중 한 곳이 없기 때문에 따로 빼서 연산

체육복을 다 빌려준 후 다시 체육복을 가진 인원 체크

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
		int answer = 0;
		
		boolean[] uniform = new boolean[n+1]; 
		for(int i=1; i<uniform.length; i++) uniform[i] = true; // 편의상 true로 해주고 싶음
		
		boolean[] extraUniform = new boolean[n+1];
	    for(int i=1; i<extraUniform.length; i++ ) { // 여벌 갖고 있는 친구들 검사
	    	for(int j=0; j<reserve.length; j++) {
	    		if(i == reserve[j]) extraUniform[i] = true;
	    	}
	    }
	    
	    for(int i=1; i<uniform.length; i++) { // 도둑 맞은 애들 검사
	    	for(int j=0; j<lost.length; j++) {
	    		if(i == lost[j]) uniform[i] = false;
	    	}
	    }
	    
	    for(int i=1; i<uniform.length; i++) { // 도둑 맞은 애들이 여벌 갖고 있으면
	    	if(uniform[i] == false && extraUniform[i] == true) {
	    		uniform[i] = true;
	    		extraUniform[i] = false;
	    	}
	    }
	    // 첫 번호와 끝 번호는 양 옆 중 한 군데가 없기 때문에 수동으로 연산
	    if(uniform[1] == true && extraUniform[1] == true 
	    && uniform[2] == false && extraUniform[2] == false) {
	    	extraUniform[1] = false;
	    	uniform[2] = true;
	    }
	    
	    for(int i=2; i<uniform.length-1; i++) { // 양 옆 애들한테 체육복 주기
	    	if(uniform[i-1] == false && extraUniform[i] == true) { // 왼쪽 먼저
	    		extraUniform[i] = false;
	    		uniform[i-1] = true;
	    	}
	    	else if(uniform[i+1] == false && extraUniform[i] == true) {
	    		extraUniform[i] = false;
	    		uniform[i+1] = true;
	    	}
	    }
	    // 끝 번호
	    if(uniform[n] == true && extraUniform[n] == true 
	    && uniform[n-1] == false && extraUniform[n-1] == false) {
	    	 extraUniform[n] = false;
	    	 uniform[n-1] = true;
	    }
	    
	    for(int i=1; i<uniform.length; i++) {
	    	if(uniform[i] == true) answer++;
	    }
        return answer;
    }
}

 

다른 사람 풀이

코드를 읽으면서 되게 잘 풀었다고 느껴졌다.

내가 boolean 배열 만들어가면서 풀었던 걸 people 배열 하나로 다 처리했다.

public int solution(int n, int[] lost, int[] reserve) {
		
        int[] people = new int[n]; // 사람 수 배열
        int answer = n; // 총 학생 수 저장

        // 각 인덱스를 학생 번호와 매칭 people[0]은 1번 학생...
        for (int l : lost) // 체육복 잃어버린 학생은 -1감소
        	               // 배열은 초기화 안해주면 기본 값이 0 → 체육복 잃어버린 학생들은 -1이 됨
            people[l-1]--;
        for (int r : reserve) 
            people[r-1]++; // 여벌 갖고있는 학생들은 1이 된다.

        // 
        for (int i = 0; i < people.length; i++) {
            if(people[i] == -1) { // 체육복 없는 애들이면
                if(i-1>=0 && people[i-1] == 1) { // i-1은 첫 실행 때 조건에 부합하지 않는다.
                	                             // → 2번 이상 학생이면서 앞 번호 학생이 여벌을 갖고 있을 경우
                    people[i]++;    // 체육복 없는 학생은 체육복 받아서 +1 여벌 빌려준 애는 -1
                    people[i-1]--;
                }else if(i+1< people.length && people[i+1] == 1) { // 마지막 번호 학생이 아니면서 내 뒷 번호가 여벌을 갖고 있다면
                    people[i]++;
                    people[i+1]--;
                }else 
                    answer--; // 체육복 없는 애 앞 뒤로 아무도 여벌이 없다면 총 학생 수에서 감소
            }
        }
        return answer;
    }