programmers.co.kr/learn/courses/30/lessons/42862
코딩테스트 연습 - 체육복
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번
programmers.co.kr
전체 학생 수 int n, 체육복을 도둑맞은 학생 번호 int[] lost, 여벌 체육복을 가져온 학생 번호 int[] reserve 가 주어진다.
도둑맞은 학생들이 여벌을 가져온 학생들에게 체육복을 빌려 입었을 때 체육수업에 가장 많이 참여할 수 있는 학생의 수를 반환해야한다.
단, 여벌을 가져온 학생은 자신의 앞, 뒤 번호 학생에게만 빌려줄 수 있다. (ex : 4번은 3, 5번에게만 빌려줄 수 있다.)
(여벌을 가져온 학생이 체육복을 도난당했을 경우 1개만 도난당한 것으로 한다.)
풀이 .
import java.util.*;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int answer = 0;
// 일단 정렬
List<Integer> lostList = new ArrayList<>();
List<Integer> reserveList = new ArrayList<>();
for (int num : lost) lostList.add(num);
for (int num : reserve) reserveList.add(num);
Collections.sort(lostList);
Collections.sort(reserveList);
// 여벌을 가져왔어도 도난당했다면 빌려줄 수 없다
for (int i = 0; i < reserveList.size(); i++) {
int num = reserveList.get(i);
if (lostList.contains(num)) {
lostList.remove((Integer) num); // remove(Object o) 사용
reserveList.remove((Integer) num);
i--; // 인덱스 당겨줘야 함
}
}
// 작은 번호에게 우선적으로 빌려준다
for (int num : reserveList) {
if (lostList.contains(num - 1)) {
lostList.remove((Integer)(num - 1));
continue;
}
if (lostList.contains(num + 1)) {
lostList.remove((Integer)(num + 1));
continue;
}
}
answer = n - lostList.size();
return answer;
}
}
여벌을 가져온 사람은 나보다 1 작은, 나보다 1 큰 사람에게 빌려줄 수 있다.
이때 무조건 나보다 작은 사람을 우선적으로 빌려주는 식으로 진행하면 된다.
반복을 돌리기 위해 정렬을 먼저 해주고 도난, 여벌 동시에 해당되는 놈들을 목록에서 제거해준다.
(주의)
ArrayList에는 remove(int index), remove(Object o) 두 가지 remove가 있다.
ArrayList<Integer> 에서는 remov(숫자)를 사용하면 무조건 remove(int index)가 호출된다.
(이것 때문에 OutOfBoundsException이 발생했다.)
remove(Object o)를 사용하고 싶다면
remove(Integer.valueOf(int)), remove(new Integer(int)) or remove((Integer) int) 세 가지 방법을 사용할 수 있다.
이유는 모르지만 마지막의 remove((Integer) int)가 가장 효율적이라고 한다.
'알고리즘 문제 > 프로그래머스' 카테고리의 다른 글
| [PG] 큰 수 만들기 JAVA (0) | 2021.01.03 |
|---|---|
| [PG] 조이스틱 JAVA (0) | 2021.01.02 |
| [PG] 카펫 JAVA (0) | 2021.01.01 |
| [PG] 소수 찾기 JAVA (0) | 2021.01.01 |
| [PG] 모의고사 JAVA (0) | 2021.01.01 |