문제 설명
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 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 |
입출력 예 설명
예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.
예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.
전략
- HashMap을 만든다.
- reserve의 값을 키로 그리고 value를 2로 설정
- lost를 forEach문으로 돌린다.
- lost-1 ~ lost +1 사이 값을 돌면서 만약 키가 있고 value가 2 이상일 시 해당 lost를 키로 value를 1로 설정한후 해당 키에는 -1한다
- HashMap의 키의 value의 총합을 구해서 리턴한다.
코드 구현
- 1차 시도
// 1차 시도
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int answer = 0;
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : reserve)
map.put(num, 2);
for ( int num: lost)
if (map.containsKey(num)) {
map.replace(num, 1);
n++;
}
for (int i = 0; i < map.size(); i++)
answer++;
return answer+n-lost.length-reserve.length;
}
}
1차 시도는 실패하였다...
뭐가 문제일까?
생각해보니 입출력에서 lost와 reserve가 오름차순으로 나온다는 보장은 없었다..
sort를 적용해 보기로 하였다.
- 2차 시도
// 2차 시도
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int answer = 0;
lost= Arrays.stream(lost).sorted().toArray();
reserve= Arrays.stream(reserve).sorted().toArray();
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : reserve)
map.put(num, 2);
for ( int num: lost)
if (map.containsKey(num)) {
map.replace(num, 1);
n++;
}
for (int i = 0; i < map.size(); i++)
answer++;
return answer+n-lost.length-reserve.length;
}
}sort를 적용한 이후 일부 테스트는 정답으로 바뀌었지만 여전히 오답으로 표기된 테스트가 있다.
문제를 찬찬히 읽어본 결과
여분을 가지고 온 학생이 도난당하는 경우의 수를 고려하지 않았다는 것을 깨달았다.
- 3차 시도
// 최종 코드
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int answer = 0;
lost= Arrays.stream(lost).sorted().toArray();
reserve= Arrays.stream(reserve).sorted().toArray();
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : reserve)
map.put(num, 2);
for ( int num: lost)
if (map.containsKey(num)) {
map.replace(num, 1);
n++;
}
for (int num : lost) {
if (map.containsKey(num - 1) && map.get(num - 1) == 2) {
map.put(num, 1);
map.replace(num - 1, 1);
} else if (map.containsKey(num + 1) && map.get(num + 1) == 2) {
map.put(num, 1);
map.replace(num + 1, 1);
}
}
for (int i = 0; i < map.size(); i++)
answer++;
return answer+n-lost.length-reserve.length;
}
}해당 내용을 고려하자 문제가 풀렸다.
