[JAVA] 프로그래머스 체육복

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

프로그래머스

 

 

 

 

 

문제 풀이 

 

- 그리디(greedy) 알고리즘은 최적해를 구하는 방법으로 여러 경우 중 하나를 결정할 때 그 순간이 최적이라고 생각되는 것을 선택하는 방식

- 때문에 항상 최적해를 보장해주진 않지만 대부분의 경우 최적해를 찾기 적합한 알고리즘이다. 

 

체육복 프로그래머스 java 자바 문제 풀이 (youtube.com)

 

 

- 여벌의 체육복을 최대한 빌려준 뒤 체육복을 가진 학생 수를 구하라 

- 여벌의 체육복을 가진 학생들 위주로 연산 

 

- Set을 활용하여 풀이 

 

1) Set 생성

 - Reserved와 lost 배열로 부터 Set를 생성 

 

2) 여분 하나씩 처리 

- Reserved에서 하나씩 꺼내서 Lost set에 줄 수 있는 사람을 찾아서 준다. 

 

3) 체육복을 가진 학생 수 계산 

- 전체 n에서 lost set의 인원을 빼서 체육복을 갖고 있는 사람 수를 반환한다. 

 

 

- 1번 학생이 빌려줄 수 있는 학생의 번호는 0번과 2인데 0번은 없으니까 2번에게 빌려줌 

- 빌려주고 나면 1과 2는 set에서 제거됨 (여분이 있지도 않고 더 이상 필요하지도 않음)

 

- 3번 학생이 빌려줄 수 있는 학생의 번호는 2번과 4번인데 2번 학생은 이미 체육복을 구했기 때문에 더 이상 필요하지 않고 4번 학생에게 빌려줌

- 3번과 4번도 set에서 제거됨

 

- 5번 학생이 빌려줄 수 있는 학생의 번호는 4번 학생과 6번학생인데 4번 학생은 이미 처리했고 6번 학생은 없음

- 5번 학생은 여분을 가진 상태에서 이 문제는 끝나게 됨

 

 

- 체육복을 가진 학생 수를 계산하기 위해서는 총 n명(5명)의 학생 중에서 lost set에 남아 있는 학생 수를 빼주면 됨

 

 

정답

 

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        
        HashSet<Integer> resList = new HashSet<>();
        HashSet<Integer> lostList = new HashSet<>();
        
        //1. set 만들기 
        for(int i : reserve)
            resList.add(i);
        for(int i : lost)
        {
            if(resList.contains(i)) //여분이 있는 학생이 도둑맞았는지를 체크해줌
                resList.remove(i); //도둑맞았다면? 여분 없는거나 다름 없음
            else
                lostList.add(i);
        }
        
        //2.여분을 기준으로 앞뒤를 확인하여 체육복을 빌려준다. 
        for(int i: resList) 
        {
            if(lostList.contains(i-1))
                lostList.remove(i-1);
            else if(lostList.contains(i+1))
                lostList.remove(i+1);
        }
        
        //3.최대한 나눠준 뒤에 lost에 남아있는 학생들은 체육복이 없는 학생들이다. 
        answer = n-lostList.size();
        
        return answer;
    }
}