프로그래머스 level 1 체육복

문제 링크

체육복

🤔 문제 이해 및 알고리즘 유형

전체 학생의 수 : n
체육복을 도난 당한 학생들의 번호가 담긴 배열 : lost
여벌의 체육복을 가져온 학생드의 번호가 담긴 배열 : reserve

출력 해야 하는 값 : 체육수업을 들을 수 있는 학생의 최댓값

조건)
제한 사항 : 전체 학생 2<=n <=30
중복 없음
여벌 체육복을 가져온 학생-> 도난-> 빌려줄 수 없음
lost와 reserve 배열은 정렬이 되어 있지 않으므로 정렬 필수!!

알고리즘 유형
Greedy(탐욕법), 구현

💡 문제 해결 방법

1) reserve 배열 안에 있는 번호가 lost 안에도 있으면 reserve에서 삭제
1-1) 이때 reserve값과 lost값 큰값으로 바꾸기
2) n에서 lost.length 빼고 num에 저장
2-1)num을 구할 때 lost.length에서 30보다 큰값이 있으면 다시 +1 해줌
3) lost for문을 돌면서 그 값의 +1 -1 한 값이 reserve에 있으면 num+=1
3-1) 이때 reserve값과 lost값 큰값으로 바꾸기

💻 코드

import java.util.Arrays;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Arrays.sort(lost);
        Arrays.sort(reserve);
        for(int i=0;i<reserve.length;i++){
            for(int j=0;j<lost.length;j++){
                if(lost[j]==reserve[i]){
                    reserve[i]=123;
                    lost[j]=123;
                }
            }
        }
        int num=0;
        for(int r=0; r<lost.length; r++){
            if(lost[r]<=30){
                num+=1;
            }
        }
        int answer = n-num;
        for(int a=0;a<lost.length;a++){
            for(int b=0;b<reserve.length;b++){
                if(lost[a]-1==reserve[b] || lost[a]+1==reserve[b]){
                    answer+=1;
                    lost[a]=-1;
                    reserve[b]=-999;
                    break;
                }
            }
        }
        return answer;
    }
}

👍 다른 사람 코드

HastSet을 이용한 풀이 방법!

import java.util.HashSet;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        /** Set을 이용해서 푸는 그리디 문제.
         *  Set은 중복 허용 x
         *  lost = 잃어버린 학생의 배열, reserve = 빌려줄 수 있는 여분 옷이 있는 학생의 배열
         *  전체 n에서 lostSet의 인원을 빼면 정답이 된다.
         */

        // 1. set을 만든다
        HashSet<Integer> reserveSet = new HashSet<>();
        HashSet<Integer> lostSet = new HashSet<>();

        for (int i : reserve)
            reserveSet.add(i);
        for (int i : lost) {
            // 중복 확인
            if (reserveSet.contains(i)) {
                reserveSet.remove(i);
            } else {
                lostSet.add(i);
            }
        }


        // 2. 여분을 기준으로 앞뒤로 확인하여 체육복을 빌려준다.
        for (int i : reserveSet) {
            if (lostSet.contains(i - 1)) {
                lostSet.remove(i - 1);
            } else if (lostSet.contains(i + 1)) {
                lostSet.remove(i + 1);
            }
        }

        // 3. 전체 학생 수에서 lostSet에 남은 학생 수를 빼주면 정답이다.
        return n - lostSet.size();
    }
}

✔ 생각해봐야 할 점

문제 조건을 꼼꼼히 읽어보자!
모든 경우의 수를 잘 고려하자, 즉 테스트케이스를 잘 작성해서 확인하자!

---

참고 사이트
https://m.blog.naver.com/sosow0212/222688948656