[프로그래머스] 탐욕법 - 체육복 (Java)

문제 링크

코딩테스트 연습 - 체육복

접근한 방법

• 탐색적 알고리즘
  - 탐욕적 선택 속성을 사용
  : 답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있다 

---

4가지 경우를 생각하여 증명해보자.

- 가정

1) 왼쪽에서 오른쪽으로 순회를 한다.

2) i번째에는 체육복이 없다.

- 체육복의 여유가 있는 4가지 경우의 수

	i-1번째	i+1번째
1	O	O
2	O	X
3	X	O
4	X	X

경우 1

순회 방향이 왼쪽부터이므로, i-1번째 이전까지는 순회가 완료된 것이다.

만약, i가 i+1에게 여벌을 받을 경우, i-1의 여벌이 남는다.

따라서, i-1에게 받아 i+1의 여벌을 여유로 남기는 것이 최적이다.

 

 

경우 2

i-1에게 여벌을 받는다.

 

 

 

경우 3

i+1에게 여벌을 받는다.

 

 

 

경우 4

받을 수 없다.

 

- 결론

1. 왼쪽에서 오른쪽으로 순회한다.

2. 왼쪽에 여벌이 있으면 왼쪽에서 체육복을 받고,
   왼쪽에 여벌이 없으면 오른쪽에서 체육복을 받는다.

---

소스코드 작성 방법

• 배열의 index는 입력이 1~5이므로, 배열의 크기를 +1하여 설정
• 학생별 체육복 갯수를 셋팅
  체육복 잃어버림 : -1
  체육복 잃어버리지 않으며, 여분이 없음 : 0
  여분이 있음 : 1
• 왼쪽에서 오른쪽 방향으로 순회
• i번째에 체육복이 없을 때,
  i-1번째에 여벌이 있으면 i-1번째에서
  i-1번째에 여벌이 없고, i+1번째에 여벌이 있으면 i+1번째에서 체육복을 받음

 

소스코드

package programmers;

import java.io.*;
import java.util.StringTokenizer;

public class Q_42862_GymClothes {
    public static int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        int[] clothes = new int[n+1]; // 체육복 현황 | -1 : 잃어버림 0 : 체육복 있음 1 : 체육복 여분 있음
        /* 체육복 갯수 셋팅 */
        // 체육복 잃어버린 학생 차감
        for (int j = 0; j < lost.length; j++)
            clothes[lost[j]] -= 1;
        // 체육복 여유있는 학생 더함
        for (int j = 0; j < reserve.length; j++)
            clothes[reserve[j]] += 1;

        /* i가 작은 순으로 체육복 넘겨주기 */
        for(int i=1 ; i<clothes.length-1 ; i++) {

            // 왼쪽에서 체육복 받음
            if(clothes[i] <0 && clothes[i-1] > 0) {
                clothes[i] ++;
                clothes[i-1] --;
            // 오른쪽에서 체육복 받음
            } else if (clothes[i] <0 && clothes[i+1] > 0){
                clothes[i] ++;
                clothes[i+1] --;
            }
            
        }

        /* 체육복이 없는 학생 카운트 */
        int minusCount = 0; 
        for(int i=1 ; i<clothes.length ; i++) {
            if(clothes[i] < 0)
                minusCount++;
        }

        answer = n - minusCount;

        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine()); // 전체 학생의 수

        StringTokenizer st = new StringTokenizer(br.readLine());
        int length = st.countTokens();
        int[] lost = new int[length]; // 체육복을 도난당한 학생들의 번호가 담긴 배열
        for (int i = 0; i < length; i++) {
            lost[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        length = st.countTokens();
        int[] reserve = new int[st.countTokens()]; // 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열
        for (int i = 0; i < length; i++) {
            reserve[i] = Integer.parseInt(st.nextToken());
        }

        bw.write(solution(n, lost, reserve)+"\n");

        br.close();
        bw.close();

    }

}