[Java] 프로그래머스 Lv1. 체육복 풀이 (탐욕법 알고리즘 Greedy Algorithm)

그리디 알고리즘

그리디 알고리즘(탐욕 알고리즘)은. 다음 단계를 생각하지 않고, 각 단계에서 가장 좋다고 생각하는 것을 선택하는 기법이다. 간단하게 아래 예시를 살펴보자. (출처: https://gomguard.tistory.com/119)

각 단계에서의 값을 더해 최대값을 구하는 문제에서, 최적해는 초록 라인을 따라가서 얻는 107이지만, 그리디 알고리즘을 이용할 경우 7보다 큰 13을 선택하고, 5와 11 중 11을 선택하여 최종적으로 24라는 값을 얻게 된다. 즉, 그리디 알고리즘이 최적해를 보장해주지는 않는다.

반드시 최적 해를 보장하지는 않지만, 그리디 알고리즘이 유효하게 먹히는 문제들이 몇몇 있다.

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한 사항

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

나의 풀이

문제의 포인트는 마지막 제한사항, 여벌 체육복을 가져온 학생이 체육복을 도난당한 경우이다. 이 경우 학생 자신은 체육 수업에 참가할 수 있으나 다른 학생에게 체육복을 빌려줄 수는 없다.

이에 for loop 을 돌리면서, reserve 배열과 lost 배열이 값이 같은 경우를 찾고, 해당 배열 값을 의미없는 수(100) 으로 바꾼다. 해당 학생은(=여벌 체육복을 가져왔으나 체육복을 도난당한 경우) 학생 자신은 체육 수업에 참가할 수 있으므로 answer를 1 증가시킨다.

데이터를 1차적으로 가공한 뒤, 그리디 알고리즘에 따라 for loop 을 돌리면서, 값이 100이 아니고, reserve 배열값 - lost 배열값의 절대값이 1인 경우 (=양 옆의 번호) 에 answer를 1 증가시킨다. 단, 예를 들어 lost = {2, 4}, reserve = {1, 3} 인 경우, 2번 학생은 1번에게 이미 체육복을 빌렸기 때문에, 3번 학생에게 또 빌릴 수는 없다. 그러므로 이미 체육복을 빌린 학생의 경우 배열 값을 의미없는 수(100)로 바꾸어 더이상 체육복을 빌릴 수 없도록 한다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

public int solution(int n, int[] lost, int[] reserve) {        int answer = 0;        //체육복을 가지고 있는 학생 수 = 전체 학생 수 - 잃어버린 학생 수 [기본적으로 수업을 들을 수 있는 학생 수]        answer = n - lost.length;                //여벌을 가져온 학생이 도난당한 경우 => 해당 학생은 체육복을 빌려줄 수는 없으나, 본인은 체육 수업을 들을 수 있음        for (int i = 0; i < reserve.length; i++) {            for (int j = 0; j < lost.length; j++) {                if(reserve[i] == lost[j]) {                    reserve[i] = 100;                     lost[j] = 100;                    answer++;                    break;                                   }            }        }                //여벌 체육복이 있는 학생은 양옆번호 학생에게 체육복을 빌려줄 수 있음. 이미 빌려주었다면 다른 학생에게는 빌려줄 수 없다.         for (int i = 0; i < reserve.length; i++) {         for (int j = 0; j < lost.length; j++) {             if(reserve[i] != 100 && lost[j] != 100) {                 if(Math.abs(reserve[i] - lost[j]) == 1) {                     reserve[i] = 100;                      lost[j] = 100;                      answer++;                      break;                                      }                         }         }     }                 return answer;     } Colored by Color Scripter

cs

다른사람의 풀이

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

public int solution(int n, int[] lost, int[] reserve) {         int answer = 0;         answer = n;           for(int i = 0; i < lost.length; i++) {             boolean rent = false;             int j = 0;             while(!rent) {                 if(j == reserve.length)                   break;                 if(lost[i] == reserve[j])                {reserve[j] = -1; rent=true;}                 else if(lost[i] - reserve[j] == 1 )      {reserve[j] = -1; rent=true;}                 else if(lost[i] - reserve[j] == -1)      {reserve[j] = -1; rent=true;}                 else                                     {j++;                      }             }             if(!rent) answer--;         }         return answer;     } Colored by Color Scripter

cs

탐욕 알고리즘에 대해 잘 와닿지가 않아서 시행착오를 좀 겪었다. 값은 맞는데 테스트를 통과하지 못해서 빌빌댔는데 고민 끝에 겨우 풀긴 풀었다. 프로그래머스 문제 풀면서, 테스트를 통과하는 것까지 고려해야하기 때문에, 어떻게 하면 효율적인 코드를 짤 수 있을까 고민을 하게 되는데, 한편으로는 너무 고민하느라 시야가 되려 좁아지는 경우가 있는 것 같다. 너무 복잡하거나 가독성 떨어지는 코드는 물론 지양해야 하겠지만, 우선 내가 아는 것을 확실히 하고 그 위에 깔끔한 코드에 대한 고민을 얹어야겠다.