문제
https://school.programmers.co.kr/learn/courses/30/lessons/42862
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 전체 학생의 수는 2명 이상 30명 이하입니다.
- 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
= 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
풀이
import java.util.*;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int answer = n - lost.length;
Arrays.sort(lost);
Arrays.sort(reserve);
List<Integer> res = new ArrayList<>();
List<Integer> loss = new ArrayList<>();
for (int i : lost) {
loss.add(i);
}
for (int i : reserve) {
res.add(i);
}
List<Integer> new_lost = new ArrayList<>();
for (int i : lost) {
if (res.contains(i)) {
answer++;
res.remove(new Integer(i));
} else new_lost.add(i);
}
for (int i : new_lost) {
if (res.contains(i - 1)) {
answer++;
res.remove(new Integer(i - 1));
continue;
}
if (res.contains(i + 1)) {
answer++;
res.remove(new Integer(i + 1));
continue;
}
}
return answer;
}
}문제 해결 과정
1. 정렬을 수행
2. 리스트 삭제 연산
- 리스트를 순회하는 과정에서 리스트 삭제 연산을 수행하였다. 예를 들어 lost = [3, 4, 5], reserve = [3, 4, 6]인 경우에 3번, 4번 학생은 체육복을 두 벌 가진 상태에서 한 벌을 잃어버린 것이므로, 처음부터 한 벌을 가진 채 도난당하지 않았다고 가정하여 문제를 풀었다.
- 이를 이용해 lost와 reserve에 모두 포함된 원소를 lost와 reserve에서 모두 제거하도록 코드를 다음과 같이 작성하였다.
for (int i : lost) {
if (reserve.contains(i)) {
answer++;
reserve.remove(new Integer(i));
lost.remove(new Integer(i));
}
}- 그러나, 이를 구현할 때, 반복문 안쪽에서 리스트 삭제 연산을 사용하면 의도와는 다르게 리스트를 순회하는 경우가 발생할 수 있다.
- 출력을 해보면 4는 중복 원소임에도 lost와 reserve에 남아 있게 된다. 3을 삭제하면서 뒤의 원소들이 앞으로 한 칸씩 당겨져 lost[0]이 4로, lost[1]이 5로 바뀌어 4에 접근하지 못했기 때문이다.
- lost 배열을 순회하며 reserve에 포함 여부를 확인하고 있기 때문에 다음과 같이 코드를 변경한다.
List<Integer> new_lost = new ArrayList<>();
for (int i : lost) {
if (reserve.contains(i)) {
answer++;
reserve.remove(new Integer(i));
} else new_lost.add(i);
}- 삭제하지 않을 원소만 담아 리스트를 갱신한다.
3. 리스트의 remove()
- remove 메서드에는 리스트의 인덱스나 삭제하려는 값을 넣을 수 있다. 이때 리스트에는 객체가 저장되어 있고 만약 Integer 타입으로 선언한 리스트일 경우 int 타입의 값을 파라미터로 넘기면 인덱스로 인식한다. 그래서
ArrayOutOfBounds에러가 발생할 수 있다. - 이를 해결하기 위해 래퍼 클래스로 감싸준다. 방법은 두 가지이다.
Integer.valueOf()메서드를 쓰거나new Integer()로 감싸준다.
Backend Developer