[Programmers] Level.1 체육복 (Java)

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

프로그래머스

 

체육복이라는 문제 Java로 풀이하겠습니다.

 

문제 설명

이 문제는 그리디 알고리즘을 사용하여 풀 수 있습니다.

그리디 알고리즘(Greedy Algorithm)은 매 순간마다 가장 좋은 선택을 하는 알고리즘입니다.

다시는 되돌아갈 수 없는 결정을 순간마다 내리는 것이 특징이에요. 이런 선택들이 모여 전체적으로 최적인 해를 찾아내는 것을 목표로 합니다.

 

문제를 해결하기 위해서는 여벌 체육복이 있는 학생과 도난당한 학생의 정보를 파악해야 합니다.

저는 다음과 같이 풀이하였습니다.

import java.util.Arrays;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int result = n - lost.length;
        Arrays.sort(lost);
        Arrays.sort(reserve);

        for (int i = 0; i < lost.length; i++) {
            for (int j = 0; j < reserve.length; j++) {
                if (lost[i] == reserve[j]) {
                    lost[i] = reserve[j] = -1;
                    result++;
                    break;
                }
            }
        }

        for (int lostP : lost) {
            for (int i = 0; i < reserve.length; i++) {
                if (reserve[i] == lostP - 1 || reserve[i] == lostP + 1) {
                    result++;
                    reserve[i] = -1;
                    break;
                }
            }
        }
        return result;
    }
}

 

1. 전체 학생의 수에서 체육복을 잃어버린 학생의 수를 뺀 값으로 result 변수의 초기값을 설정합니다.
2. 체육복을 도난당한 학생들의 번호가 담긴 lost와 여벌의 체육복을 가져온 학생들의 번호가 담긴 reserve 배열을 정렬합니다.
3. 먼저 여분의 체육복을 가져온 학생이 체육복을 도난당했을 경우에는 빌려줄 수 없으므로 lost 배열은 순회하면서 reserve에 해당 학생이 있는지 확인해 줍니다.
   - 이 경우에 해당할 경우 result 변수에 학생의 수를 더해준 후 해당 학생을 -1으로 설정합니다.
4. 다시 도난당한 lost 배열을 순회하면서 앞뒤로 여벌의 체육복이 있는 경우가 있는지 확인해 줍니다.
   - 이 경우에 해당할 경우 result 변수에 학생의 수를 더해준 후 해당 학생을 -1으로 설정합니다.
5. result에 담긴 체육복을 입은 학생 수를 반환합니다.

 

주어진 배열을 정렬하고 반복문을 사용하여 문제를 풀이할 수 있었습니다.

 

다른 이견이 있으시다면 댓글로 자유롭게 남겨주세요.