[프로그래머스] 탐욕법(Greedy) Lv1.체육복

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

1시간동안 시간을 정해서 풀었고 50분 정도가 걸렸다
시간재고 풀다보니 스케치 시간도 조금 줄이려고 글씨를 날려써버렸다..!

정리

1. 체육 수업을 들을 수 있는 학생 수 answer의 초기값은 n - lost.size()

2. lost에 있는 학생들을 없앨 수 있냐 없냐의 문제로 해결

• lost를 앞에서부터 순회하면서 앞, 뒤 번호의 학생이 reserve에 있는지 확인
• 앞 번호의 학생이 있으면 lost에서 삭제하고 answer++, 뒤 번호의 학생은 확인하지 않음
• 앞 번호의 학생이 없으면 뒤 번호의 학생이 있는지 확인, 있으면 lost에서 삭제하고 answer++
• 앞, 뒤 번호의 학생이 reserve에 다 없다면 lost에서 없앨 수 없음.

3. 예외처리

• lost와 reserve에 똑같은 학생이 있는 경우 두 벡터에서 모두 삭제하고 answer++
• reserve에 있으나 여벌을 하나 잃어버려서 다른 학생에게 빌려줄 수 없으므로!

처음에 앞, 뒤번호의 학생이 모두 빌려줄 수 있는 경우의 수를 고려해야 하나? 싶었다.
예를 들어 3번 학생이 여벌이 있다면 2번과 4번에게 모두 빌려줄 수 있는데,
2번에게 빌려줄 수 있는 경우과 4번에게 빌려줄 수 있는 경우 모두 따져야 하나? 생각이 들면서
막 꼬이고 복잡해질 뻔했지만,,

예전에 '알고리즘 문제 해결 전략'에서 순서 강제를 통해 문제를 단순화하는 방법을 봤던 게 생각이 났다!
그래서 임의의 학생의 앞, 뒤번호의 학생에게 모두 여벌이 있더라도
무조건 앞 번호 학생의 체육복을 빌리는 것으로 강제했다

예외처리할 때에는 지난 문제에서 배웠던 STL의 set_intersection() 함수를 사용했다
lost와 reserve의 중복원소를 찾아서 삭제한 다음 학생수만 늘리기 위함이었다.

그런데 살짝 실수했던 게
원래 set_intersection() 는 정렬된 벡터에 대해 사용해야 하는데
프로그래머스 예제에는 이미 배열이 정렬된 채로 입력되는 것들만 보여서 sort()를 안했었다
근데 자꾸 애매하게 몇 몇 테스트케이스에서만 오류가 나서 혹시..?싶어 sort()를 해주었더니 전부 통과할 수 있었다.

set_intersection()을 쓸 때에는 문제에서 이미 정렬된 배열을 준다고 명시되어있지 않은 이상
무조건 sort를 사용해야할 것 같다!

(여담이지만)
오늘 스터디에서 지난 번 문제(뉴스 클러스터링)를 푼 다른 친구의 방식도 리뷰했는데
실제 교집합과 합집합을 만들지 않고도 문제를 풀 수 있어서
추가적인 공간을 사용하지 않아도 되는 그런 방식도 괜찮아보였다!
실제 교집합이 필요하다기 보다는 교집합 원소의 개수가 필요했던 것이기 때문에..!

배운 점
1. find()

• find()는 벡터에서 찾으려는 원소의 첫 번째 위치를 반환한다
• 찾지 못하면 end()를 반환하기 때문에 if문으로 lost.end()가 아닐 경우에만 특정 처리를 하도록 조건을 걸 수 있다

2. erase()

• erase()는 매개변수로 범위를 지정하면 해당 범위 안에 있는 원소들을 삭제할 수 있고,
  하나의 매개변수로 iter만을 넣으면 해당 위치의 원소를 삭제할 수 있다

CODE

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
 
   int answer = 0;
   answer = n - lost.size();

   vector<int> ::iterator iter;
   vector<int> ::iterator tmpIter;
 
   sort(lost.begin(), lost.end());
   sort(reserve.begin(), reserve.end());
 
   // 예외처리: 만약 reserve랑 lost에 똑같은 학생이 있으면
   // reserve와 lost에서 지워주고 수업받을 수 있는 학생의 수인 answer에는 더해주어야 함 
 
   vector<int> inter(lost.size()+reserve.size());
   auto i_iter = set_intersection(lost.begin(), lost.end(), reserve.begin(), reserve.end(), inter.begin());
   inter.erase(i_iter, inter.end());

   vector<int> ::iterator interIter;
   if(inter.size() > 0)
   {
       for (interIter = inter.begin(); interIter != inter.end(); interIter++)
       {
           iter = find(lost.begin(), lost.end(), *interIter);
           if (iter != lost.end())
           {
               lost.erase(iter);
           }
           iter = find(reserve.begin(), reserve.end(), *interIter);
           if (iter != reserve.end())
           {
               reserve.erase(iter);
               answer++;
           }
       }
   }
   

   for(iter = lost.begin(); iter != lost.end(); iter++)
   {
       int curStudent = *iter;
       tmpIter = find(reserve.begin(), reserve.end(), curStudent-1);
       if(tmpIter != reserve.end())
       {
           reserve.erase(tmpIter);
           answer++;
       }
       else
       {
           tmpIter = find(reserve.begin(), reserve.end(), curStudent+1);
           if (tmpIter != reserve.end())
           {
               reserve.erase(tmpIter);
               answer++;
           }
       }
   }

   cout<<answer<<endl;
   return answer;
}