6day.algo.noah 체육복

놀아·2020년 12월 11일

하루알고리즘 (Java)

목록 보기

6/15

💻문제소개

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

전체 학생의 수는 2명 이상 30명 이하입니다.
체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

n lost reserve return

5 [2, 4] [3] 4

5 [2, 4] [1, 3, 5] 5

3 [3] [1] 2

n	lost	reserve	return
5	[2, 4]	[3]	4
5	[2, 4]	[1, 3, 5]	5
3	[3]	[1]	2

😪나만의 문제정의

체육수업을 들을 수 있는 사람 == 여분의 체육복을 있는 경우
(전체 학생수) - (도난당한 학생 수) + (도난 당한 학생중 여벌 옷을 가지고 있던 학생 수) + (다른 학생으로부터 체육복을 받은 학생 수) = answer

😶문제풀이

🎈 그리디 풀이 (1차시)

이번에도 이해를 못해서 참고를 했다.

  public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        int lost1 = 0; // 여분이 있고 도난당한 경우
        int count = 0;
        
        for(int i = 0 ; i < lost.length ; i++){ // 같은 사람이 도난과 여분이 있을경우
            for(int j = 0 ; j < reserve.length ; j++){
                if(lost[i] == reserve[j]){
                    lost1++;
                    lost[i] = -1;
                    reserve[j] = -1;
                }
            }
        }
        
        /* 빌려주는 사람(reserve 요소) 앞뒤 번호를 비교(lost) 후 있으면 count++ */
        for(int i = 0; i < lost.length ; i ++){
            for(int j = 0 ; j < reserve.length ; j++){
                if(lost[i]==reserve[j]+1 || lost[i]==reserve[j]-1) { 
                    count++;
                    reserve[j] = -1;
                    break;
                }
            }
        }
        /* answer = (전체 학생수) - (도난당한 학생 수) + 
        (도난 당한 학생중 여벌 옷을 가지고 있던 학생 수) + (다른 학생으로부터 체육복을 받은 학생 수)*/
        answer = n - lost.length + lost1 + count;
        
        return answer;
    }
    
//참고 https://ju-nam2.tistory.com/4

😂 그리디 결과 (1차시)

나는 코드실행해서 결과는 통과였는데, 채점을 해보니 실패라고 뜨는 것이었다.. 다시 도전하기로 했다.

🎈 그리디 풀이 (2차시)

반복 숙달로 이 문제는 외웠다! 이렇게라도 풀어서 다행이다.

public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        int[] student = new int[n];
        
        // 초기화 코드 
        for(int i = 0 ; i < n ; i++){
            student[i] = 1;
        }
        
        // 도난 학생 
        for(int i : lost){
            student[i-1]--;
        }
        
        // 여분 학생
        for(int i : reserve){
            student[i-1]++;
        } 
    
        for(int i = 0; i < n ; i++){
            if(student[i] == 0){ // 도난 당한학생
                if(i-1 >= 0 && student[i-1] > 1){ // 왼쪽학생 빌려주고, 없음 처리
                    student[i]++;
                    student[i-1]--;
                }else if(i+1 < n && student[i+1] > 1){ // 오른쪽학생 빌려주고, 없음 처리
                    student[i]++;
                    student[i+1]--;
                }
            }
        }
        
        for(int i : student){
            if(i > 0){
                answer += 1;
            }
        }
        
        return answer;
    }
    
//참고 https://binghedev.tistory.com/75

😂 그리디 결과 (2차시)

알고리즘은 이렇게 반복이 실력향상에 도움이 되는 것 같다. 추가로 탐욕 알고리즘에 대해 남길 것이다.

탐욕 알고리즘 (greedy algorithm)

최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. [출처: 위키백과]

최적해를 가지기위한 식을 세우기가 어려운거 같다. 초등학교 때도 못한 식세우기... 익숙해지는 것 밖에 없다고 생각한다.