Picking Numbers
문제: Picking Numbers
난이도: Easy
문제 설명
주어진 정수형 배열에서 둘의 차가 1이하인 정수 두 가지만을 요소로 갖는 배열 중 길이가 가장 긴 경우의 길이를 출력하여라.
예를 들어 배열 a = [1, 1, 2, 2, 4, 4, 5, 5, 5]의 경우는 [1, 1, 2, 2], [4, 4, 5, 5, 5] 두 가지 배열이 만들어질 수 있다. 그리고 두 배열 중 가장 길이가 긴 경우는 [4, 4, 5, 5, 5]의 5이다.
문제 해결
소스 코드
public static int pickingNumbers(List<Integer> a) {
List<Integer> values = new ArrayList<Integer>();
int max = 0;
int maxTemp = 0;
for(int i = 0; i < a.size(); i++) {
if(!values.contains(a.get(i))) {
values.add(a.get(i));
}
}
for(int i = 0; i < values.size(); i++) {
for(int j = 0; j < a.size(); j++) {
if(Math.abs(values.get(i) - a.get(j)) <= 1 && values.get(i) >= a.get(j)) {
maxTemp++;
}
}
if(maxTemp > max) {
max = maxTemp;
}
maxTemp = 0;
}
return max;
}
해설
먼저 주어진 ArrayList a에서 값을 하나씩만 뽑아 중복을 제거한 새로운 ArrayList인 values를 만들었다. 그 후 values에 있는 각각의 값들과 a의 값들을 비교해 차가 1이하인 경우마다 maxTemp값을 1 증가시켰다.
values의 한 값과 a의 모든 값의 비교가 끝날 때마다 max와 maxTemp를 비교하여 maxTemp가 max보다 크면 max의 값을 maxTemp의 값으로 갱신한다.
values의 한 값과 a의 값들을 비교하는 if문에서 values의 값이 a의 값보다 크거나 같은 경우를 넣은 이유는 values의 한 값과 차이가 1이하인 조건만 있을 경우 세 가지 값이 선택될 수가 있기 때문이다. 예를 들어 values에서 꺼낸 값이 3이고 a = [2, 2, 3, 3, 3, 4, 5]일 경우 2와 4 모두 3과의 차가 1 이하여서 원래 나와야 할 결과인 [2, 2, 3, 3, 3], 길이 5가 아닌 [2, 2, 3, 3, 3, 4], 길이 6으로 결과가 나올 수 있다.