[프로그래머스/C++] 체육복
체육복
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 전체 학생의 수는 2명 이상 30명 이하입니다.
- 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
- 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
입출력 예
| n | lost | reserve | return |
|---|---|---|---|
| 5 | [2, 4] | [1, 3, 5] | 5 |
| 5 | [2, 4] | [3] | 4 |
| 3 | [3] | [1] | 2 |
풀이
각 배열을 정렬하면 바로 직전의 번호를 가진 학생, 바로 다음의 번호를 가진 학생의 체육복 수가 2개인지 차례로 검사하는 방법을 통해 구할 수 있다. 가장 중요한 것은 마지막 제한사항인데, 이걸 안읽어서 계속 고민했다. 문제를 꼼꼼하게 읽어야 한다는 좋은 교훈을 준 문제다. 일단 생각나는데로, reserve와 lost에 동시에 포함되어있는 학생의 번호를 두 배열 모두에게서 제거한 후 바로 위의 로직을 수행하도록 코드를 짜보았다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
sort(lost.begin(), lost.end()); sort(reserve.begin(), reserve.end());
for (vector<int>::size_type i = 0; i < reserve.size(); ++i) {
vector<int>::iterator justOneLeft = find(lost.begin(), lost.end(), reserve[i]);
if(justOneLeft != lost.end()) {
lost.erase(justOneLeft);
reserve.erase(reserve.begin() + i);
--i;
}
}
int answer = n - lost.size();
for (vector<int>::size_type i = 0; i < lost.size(); ++i) {
vector<int>::iterator prev = find(reserve.begin(), reserve.end(), lost[i] - 1);
vector<int>::iterator next = find(reserve.begin(), reserve.end(), lost[i] + 1);
if (prev != reserve.end()) {
reserve.erase(prev);
++answer;
}
else if(next != reserve.end()) {
reserve.erase(next);
++answer;
}
}
return answer;
}
보시다시피 코드가 많이 더럽다. 다른 사람의 풀이를 보니 좋아요를 가장 많이 받은 풀이가 다음과 같은데,
#include <string>
#include <vector>
using namespace std;
int student[35];
int solution(int n, vector<int> lost, vector<int> reserve) {
int answer = 0;
for(int i : reserve) student[i] += 1;
for(int i : lost) student[i] += -1;
for(int i = 1; i <= n; i++) {
if(student[i] == -1) {
if(student[i-1] == 1)
student[i-1] = student[i] = 0;
else if(student[i+1] == 1)
student[i] = student[i+1] = 0;
}
}
for(int i = 1; i <=n; i++)
if(student[i] != -1) answer++;
return answer;
}
문제의 마지막 조건은… 이렇게 풀라고 힌트를 준 것이었다. 그 왜, 다른 문제들을 풀 때 보편적으로 전역 변수로 배열을 하나 크게 잡고 그걸로 계산하지 않는가. 시간은 나랑 비슷하게 0.01ms로 나왔는데 이게…더 빠른가? find함수랑 erase함수가 O(n)시간복잡도면 확실히 이게 더 빠른거긴 한데, 일단 아름다운 코드니까 누구든 이걸 뽑을 것 같다. 목적에 충실한 코드.
끝
댓글남기기