두 개 뽑아서 더하기(level1)
프로그래머스 level1 문제인 두 개 뽑아서 더하기 문제입니다.
문제를 간단히 소개하자면 다음과 같습니다.
array = { 1, 2, 4, 3, 1};
1 + 2 = 3
1 + 4 = 5
....
result = { 2, 3, 4, 5, 6, 7}; 말그대로 두 개를 뽑아서 더하고 중복제거와 오름차순 정렬을 시켜주어야 했습니다.
결과에 대한 시간비율만 적도록 하겠습니다.
contains()
contains( )는 요소가 있으면 true, 없다면 false를 반환값으로 삼는 매서드입니다.
- 풀이 순서 -
1. Arrays.sort(int[]) : 오름차순으로 선 정렬
2. 이중for문(contains가 false인 경우에만 Array에 add)
3. 반환값이 int[] 타입이기에 for문을 이용한 copy
contains가 false인 경우는 "중복된 값이 존재하지 않는다." 라는 뜻입니다.
- 결과 -
테스트 1 〉 통과 (0.50ms, 53MB)
테스트 2 〉 실패 (0.51ms, 53.8MB)
테스트 3 〉 통과 (0.49ms, 52.2MB)
테스트 4 〉 실패 (0.59ms, 52.8MB)
테스트 5 〉 실패 (0.65ms, 52.4MB)
테스트 6 〉 실패 (1.85ms, 53.3MB)
테스트 7 〉 실패 (13.72ms, 52.8MB)
테스트 8 〉 통과 (3.38ms, 51.9MB)
테스트 9 〉 통과 (2.02ms, 55.8MB)
결과는 올바르게 나왔지만 테스트에는 실패하였습니다.
indexOf()
indexOf( )는 요소가 있으면 해당 index 값 , 없다면 -1을 반환값으로 삼는 매서드입니다.
- 풀이 순서 -
1. 풀이순서는 contains()와 동일
2. 단, if문은 if( array.indexOf( 두수의 합 ) < 0 ) 으로 주어 -1인 경우가 중복이 없다는 것을 조건했습니다.
- 결과 -
테스트 1 〉 통과 (0.48ms, 52.7MB)
테스트 2 〉 실패 (0.50ms, 51.8MB) - 0.01ms
테스트 3 〉 통과 (0.41ms, 52.5MB)
테스트 4 〉 실패 (0.58ms, 52.3MB) - 0.01ms
테스트 5 〉 실패 (0.57ms, 52.8MB) - 0.08ms
테스트 6 〉 실패 (1.27ms, 52.7MB) - 0.58ms
테스트 7 〉 실패 (6.22ms, 53.2MB) - 7.50ms
테스트 8 〉 통과 (3.59ms, 53.3MB)
테스트 9 〉 통과 (2.52ms, 52.2MB)
contains() 보다는 대략 2배가량 빠른 수치를 보여주고 있었습니다. 하지만 테스트를 실패했습니다.
HashSet
시간이 오래걸리는 이유가 별도로 중복제거를 하고있는 역할인 if문의 조건이 문제라고 생각했습니다.
contains()나 indexOf()는 다시 리스트를 탐색하여 있는지 없는지 부하를 걸기 때문에 자동적으로 중복을 제거해주는 Set을 이용하기로 했고 그 중 가장 빠르다는 HashSet 객체를 사용했습니다.
기존의 ArrayList로 선언한 부분만 HashSet으로 변경해주었습니다.
- 결과 -
테스트 1 〉 통과 (0.53ms, 52.7MB)
테스트 2 〉 실패 (0.59ms, 53.1MB) +0.09ms
테스트 3 〉 실패 (0.48ms, 52.2MB) +0.07ms ( 갑자기? )
테스트 4 〉 실패 (0.51ms, 52.3MB) -0.07ms
테스트 5 〉 실패 (0.54ms, 52.2MB) -0.04ms
테스트 6 〉 통과 (0.61ms, 52.7MB) -0.66ms
테스트 7 〉 통과 (1.96ms, 52.1MB) -4.26ms
테스트 8 〉 통과 (1.40ms, 52.3MB)
테스트 9 〉 통과 (2.51ms, 52.6MB)
결과가 이해가 안되었고, 속도도 불분명하여 Arrays.sort( )를 제거해주었습니다.
Arrays.sort() 제거
- 결과 -
테스트 1 〉 통과 (0.06ms, 52.5MB)
테스트 2 〉 실패 (0.07ms, 52MB) - 0.52ms
테스트 3 〉 실패 (0.05ms, 52.8MB) - 0.42ms
테스트 4 〉 실패 (0.07ms, 52.2MB) - 0.44ms
테스트 5 〉 실패 (0.07ms, 52MB) - 0.47ms
테스트 6 〉 통과 (0.28ms, 52.5MB)
테스트 7 〉 통과 (1.91ms, 52.8MB)
테스트 8 〉 통과 (1.12ms, 52.7MB)
테스트 9 〉 통과 (0.96ms, 52.7MB)
속도가 눈에 띄게 떨어졌습니다.
하지만 실패한 결과들을 보니 정렬이 안되어 문제가 틀렸다고 판단되는 것 같습니다.
그래서 최소한의 방법인 정렬과 중복제거를 동시에 해주는 TreeSet을 적용시켜보았습니다.
TreeSet
최종적으로 Set에서 TreeSet을 적용했습니다.
중복도 제거해주는 특징과 정렬된 상태를 유지하기 때문에 매우 빠르다고 합니다.
- 결과 -
테스트 1 〉 통과 (0.67ms, 52.7MB)
테스트 2 〉 통과 (0.74ms, 52.3MB)
테스트 3 〉 통과 (0.75ms, 52.3MB)
테스트 4 〉 통과 (0.99ms, 52.7MB)
테스트 5 〉 통과 (0.83ms, 51.8MB)
테스트 6 〉 통과 (1.30ms, 53.4MB)
테스트 7 〉 통과 (5.06ms, 52.8MB)
테스트 8 〉 통과 (3.08ms, 52.8MB)
테스트 9 〉 통과 (2.93ms, 51.8MB)
모두 통과했습니다.
- 소스코드 -
import java.util.*;
public static int[] solution(int[] numbers) {
TreeSet<Integer> treeSet = new TreeSet<Integer>();
for(int i=0; i<numbers.length-1; i++){
for(int j=i+1; j<numbers.length; j++){
treeSet.add(numbers[i] + numbers[j]);
}
}
int[] answer = new int[treeSet.size()];
int z = 0;
for(int object : treeSet){
answer[z++] = object;
}
return answer;
}