프로그래머스 - 체육복
구해야 하는 것
- 학생들끼리 체육복을 적절히 빌렸을 때 체육수업을 들을 수 있는 학생의 최댓값
주어진 자료
- 전체 학생의 수 = n
- 체육복을 도난당한 학생들의 번호가 담긴 배열 = lost
- 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 = reverse
조건
- 체육복은 바로 앞번호나 뒷번호의 학생에게만 빌려줄 수 있다.
- 전체 학생 수는 2 이상 30 이하
- 체육복을 도난당한 학생 수는 1 이상 n 이하, 중복 없음
- 여벌 체육복을 가져온 학생 수는 1 이상 n 이하, 중복 없음
- 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있다.
- 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수도 있는데, 그러면 남은 체육복이 1개이므로 다른 학생에게 빌려줄 수 없다.
문제를 더 단순하게 하기 위해서 주어진 조건 버리기
- 체육복은 바로 앞번호나 뒷번호의 학생에게만 빌려줄 수 있다.
- 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수도 있는데, 그러면 남은 체육복이 1개이므로 다른 학생에게 빌려줄 수 없다.
다른 조건들은 당연한 얘기라, 이 두 조건에 유의하면서 풀어야겠다.
계획
- 체육복 개수를 저장할 배열 have를 만들고, 모든 원소를 1로 초기화한다.
(도난 당하지도 않고, 여벌 체육복을 가져오지도 않은 초기 상태. 모두 체육복 1벌씩 가지고 있음)
각 학생의 번호를 have의 인덱스로 사용한다. - have에서 도난 당한 학생들의 체육복 수를 1 감소시킨다.
- have에서 여벌을 가져온 학생들의 체육복 수를 1 증가시킨다.
- for문을 돌면서 have[i]의 값이 0인 경우(도난 당한 학생), 앞 번호 학생(have[i - 1])이나 뒷 번호 학생(have[i + 1])의 값이 2이면 해당 학생의 값을 1 감소시키면서 have[i]의 값을 1 증가시킨다.
- for문을 돌면서 have[i]의 값이 1 이상이면 answer를 1 증가시킨다.
- answer를 return 한다.
실행
int solution(int n, vector<int> lost, vector<int> reserve) {
int answer = 0;
int have[31];
int reserveStudent = 0;
int lostStudent = 0;
fill_n(have, 31, 1); // 1로 초기화
// 도난 당한 학생들은 have 1 감소
for(int i = 0; i < lost.size(); i++) {
have[lost[i]]--;
}
// 여벌을 가져온 학생들은 have 1 증가
for(int i = 0; i < reserve.size(); i++) {
have[reserve[i]]++;
}
for(int i = 1; i <= n; i++) {
if(have[i] == 0) { // 도난 당한 학생
if(have[i - 1] == 2) {
have[i - 1]--;
have[i]++;
}
else if(have[i + 1] == 2) {
have[i + 1]--;
have[i]++;
}
}
}
for(int i = 1; i <= n; i++) {
if(have[i] >= 1) { // 체육복 1개 이상인 학생들은 체육 수업 들을 수 있음
answer++;
}
}
return answer;
}
반성
- 처음에 '체육복은 바로 앞번호나 뒷번호의 학생에게만 빌려줄 수 있다.'라는 조건을 까먹고 계획을 세우다가, 해당 조건이 빠졌다는걸 깨닫고 계획을 수정했다.
조건이 좀 많은 경우에는 굳이 고려하지 않아도 되는 당연한 조건들을 먼저 버리고 시작해야겠다.