[코딩테스트] Java 체육복

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

그리디접근법으로 문제를 풀었습니다. 그리디는 정렬을 필요로하는 문제가 많습니다. 최적의 해를 구해야하기 때문입니다.

소스코드

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int len = lost.length;
        int answer= n - len;
        Set<Integer> clothes = new HashSet<Integer>();
        boolean[] visited = new boolean[len];
        
        for(int num : reserve) {
            clothes.add(num);
        }
        
        Arrays.sort(lost);
        for(int i = 0; i < len; i++) {
            if(clothes.contains(lost[i])) {
                answer++;
                visited[i] = true;
                clothes.remove(lost[i]);
            }
        }


        for(int i = len - 1; i >= 0; i--) {
            if (visited[i]) continue;
            
            if(clothes.contains(lost[i] + 1)) {
                clothes.remove(lost[i] + 1);
                answer++;
            } else if(clothes.contains(lost[i] - 1)) {
                clothes.remove(lost[i] - 1);
                answer++;
            }
        }


        return answer;
    }
}

코드 설명

• 초기화
  • n: 전체 학생 수.
  • len: lost 배열의 길이 (즉, 체육복을 잃어버린 학생들의 수).
  • answer: 체육수업에 참여할 수 있는 학생의 수 (초기값은 전체 학생 수에서 체육복을 잃어버린 학생 수를 뺀 값으로 설정됨).
  • clothes: 여벌 체육복을 가진 학생들의 번호를 저장할 HashSet 객체.
  • visited: lost 배열의 각 학생들이 여벌 체육복을 빌려서 해결되었는지 확인하는 배열.
• Set<Integer> clothes = new HashSet<Integer>(); for(int num : reserve) { clothes.add(num); }
  • reserve 배열을 순회하여 여벌 체육복을 가진 학생들의 번호를 clothes HashSet에 추가합니다. 이로써 여벌 체육복을 가진 학생들을 빠르게 찾을 수 있게 됩니다.
• for(int i = 0; i < len; i++) { if(clothes.contains(lost[i])) { answer++; visited[i] = true; clothes.remove(lost[i]); } }
  • 체육복을 잃어버린 학생 중 여벌 체육복이 있는 학생을 처리합니다.
• 두번째 for문
  • 여벌 체육복을 빌려주지 않은 학생들에게 체육복을 빌려주는 부분입니다.
  • visited[i]가 false인 학생들에 대해 여벌 체육복을 빌려줄 수 있는지 확인합니다.
  • lost[i] + 1 또는 lost[i] - 1이 여벌 체육복을 가진 학생 목록(clothes)에 있으면 해당 학생에게 체육복을 빌려줍니다.
  • 이때 clothes.remove(lost[i] + 1) 또는 clothes.remove(lost[i] - 1)로 여벌 체육복을 빌려준 학생을 제거하고, answer를 증가시킵니다.