두 개 뽑아서 더하기
문제
https://school.programmers.co.kr/learn/courses/30/lessons/68644
풀이
- 이중 for문을 통해 모든 합을 구하고, Set 컬랙션을 통해 중복되지 않도록 한다.
하지만 같은 인덱스끼리는 합하지 않는다.
- 해당 Set 컬렉션을 int 배열로 전환하면서 sort를 하여 오름차순으로 정렬한다.
Stream API를 사용하여 처리한다.
class Solution {
public int[] solution(int[] numbers) {
Set<Integer> nums = new HashSet<>();
for (int i=0; i<numbers.length-1; i++) {
for (int j=i; j<numbers.length; j++) {
nums.add(numbers[i] + numbers[j]);
}
}
return nums.stream()
.mapToInt(Integer::intValue)
.sorted().toArray();
}
}테스트 1 〉 통과 (2.50ms, 91.8MB)
테스트 2 〉 통과 (2.41ms, 81.8MB)
테스트 3 〉 통과 (2.48ms, 85MB)
테스트 4 〉 통과 (2.45ms, 85.8MB)
테스트 5 〉 통과 (2.50ms, 85.5MB)
테스트 6 〉 통과 (2.76ms, 84.2MB)
테스트 7 〉 통과 (4.31ms, 89.6MB)
테스트 8 〉 통과 (3.37ms, 92.4MB)
테스트 9 〉 통과 (2.93ms, 70.9MB)평균적으로 약 3ms가 걸리는거 같다.
TreeSet의 사용
TreeSet은 HashSet과 달리 정렬된 순서로 요소가 정리된다.
즉, 요소를 중복 없이 저장하면서 자동으로 정렬된 상태를 유지한다.
마지막에 stream()에서 sorted() 함수를 사용하지 않아도 된다.
import java.util.*;
class Solution {
public int[] solution(int[] numbers) {
Set<Integer> nums = new TreeSet<>();
for (int i=0; i<numbers.length-1; i++) {
for (int j=i+1; j<numbers.length; j++) {
nums.add(numbers[i] + numbers[j]);
}
}
return nums.stream()
.mapToInt(Integer::intValue)
.toArray();
}
}하지만 그렇다고 더 빠른가?
그렇다고 말할 수는 없다. TreeSet은 데이터를 삽입하고 정렬하는 데까지 시간이 걸리기 때문에, 데이터가 많으면 많을수록 HashSet이 더 빠르다고 한다.
테스트 1 〉 통과 (2.45ms, 90.2MB)
테스트 2 〉 통과 (2.42ms, 87MB)
테스트 3 〉 통과 (2.38ms, 73.1MB)
테스트 4 〉 통과 (2.65ms, 76.7MB)
테스트 5 〉 통과 (3.36ms, 87.8MB)
테스트 6 〉 통과 (4.14ms, 82.8MB)
테스트 7 〉 통과 (4.68ms, 85.2MB)
테스트 8 〉 통과 (4.13ms, 79.4MB)
테스트 9 〉 통과 (3.46ms, 76MB)동일하게 평균적으로 약 3ms가 소요된다.
Stream API vs For
위에 코드들은 모두 Stream으로 처리했다.
Java의 Stream API는 함수형 인터페이스를 통해 직관적으로 처리할 수 있도록 도와주는 API이다.
즉, "어떻게" 가 아닌 "무엇을" 할 지에 대해 명시한다.
위에서 작성한 Stream 형식도 보면
nums.stream()
.mapToInt(Integer::intValue) //Integer 참조형 변수를 int 기본형 변수로 매핑
.sorted() //정렬
.toArray(); //배열로 반환함수를 명시적으로 사용함으로써 어떤 작동을 할 것인지가 확실하게 보인다.
가독성은 좋지만, 사실 속도 면에서는 굉장히 느리다.
이유는 내부적으로 람다 객체(추상화)를 생성하고, 파이프라인을 따로 구성하는 부분에서 비용이 발생한다.
따라서 Stream은 중간 연산이 많이 필요할 때 사용하는 것이 좋다.
그렇다면 이 부분을 Iterator를 사용하여 Stream이 아닌 직접 배열 안에 값을 넣도록 수정해보자.
class Solution {
public int[] solution(int[] numbers) {
Set<Integer> nums = new HashSet<>();
for (int i=0; i<numbers.length-1; i++) {
for (int j=i+1; j<numbers.length; j++) {
nums.add(numbers[i] + numbers[j]);
}
}
//변경된 부분!
int [] answer = new int[nums.size()];
int index = 0;
for (Integer num : nums) {
answer[index++] = num;
}
Arrays.sort(answer);
return answer;
}
}결과는?
테스트 1 〉 통과 (0.57ms, 74.4MB)
테스트 2 〉 통과 (0.35ms, 88.1MB)
테스트 3 〉 통과 (0.36ms, 74.6MB)
테스트 4 〉 통과 (0.40ms, 70.5MB)
테스트 5 〉 통과 (0.44ms, 74.8MB)
테스트 6 〉 통과 (0.81ms, 87.5MB)
테스트 7 〉 통과 (1.57ms, 80.8MB)
테스트 8 〉 통과 (0.94ms, 69.5MB)
테스트 9 〉 통과 (0.92ms, 88MB)약 1ms도 걸리지 않는 빠름을 보여준다... !!
반환 형식 변경
다른 사람들의 풀이를 보면서 알았는데.. 프로그래머스 반환 형식을 변경할 수 있다..!
주로 컬랙션이 아닌 배열로 반환하도록 설정되어 있어.. toArray() 메서드를 사용해야 했는데,, 그냥 반환 형식을 변경하면 되는 거였다.
하긴 입출력만 맞추면 되긴 하겠네..
쉽게 ArrayList<Integer> 로 반환 형식을 변경하여 사용하게 되면?
import java.util.*;
class Solution {
public ArrayList<Integer> solution(int[] numbers) {
Set<Integer> nums = new HashSet<>();
for (int i=0; i<numbers.length-1; i++) {
for (int j=i+1; j<numbers.length; j++) {
nums.add(numbers[i] + numbers[j]);
}
}
ArrayList<Integer> answer = new ArrayList<>();
for (Integer num : nums) {
answer.add(num);
}
Collections.sort(answer);
return answer;
}
}테스트 1 〉 통과 (0.12ms, 79.7MB)
테스트 2 〉 통과 (0.21ms, 86.2MB)
테스트 3 〉 통과 (0.09ms, 74MB)
테스트 4 〉 통과 (0.13ms, 81.3MB)
테스트 5 〉 통과 (0.19ms, 72.8MB)
테스트 6 〉 통과 (0.31ms, 82.1MB)
테스트 7 〉 통과 (1.42ms, 81.4MB)
테스트 8 〉 통과 (0.76ms, 85.9MB)
테스트 9 〉 통과 (1.01ms, 76.1MB)거의 대부분 0ms에 가까운 시간을 소요하는 것을 볼 수 있다..!!!
- 왜 컬랙션으로 처리하는 것이 더 빠른걸까?
사실 컬랙션이 더 빠르다는 것보다는
Integer 그대로 사용했냐,
Integer를 int로 변경해서 사용했냐의 차이다.
GPT🗣️
두 코드 모두Set<Integer>nums를 정렬 가능한 컬렉션으로 옮기고 정렬한 뒤 반환하지만,
아래쪽(ArrayList) 코드가 더 빠른 이유는 아주 미묘한 "언박싱과 배열 복사 비용"의 차이 때문입니다.
int[] answer = new int[nums.size()];
for (Integer num : nums) {
answer[index++] = num; // Integer → int: 언박싱 발생
}이 과정에서 JVM 내부적으로 null 체크와 value를 가져오는 작업이 필요하다.
Wrapper Class
Wrapper Class는 각각 타입에 해당하는 데이터를 인수로 전달받아, 해당 값을 가지는 객체로 만들어준다.
종류로는 Integer, Boolean, Long .. 등등, 내부적으로 다양한 메서드가 존재한다.
Integer는 Wrapper Class, 참조형 변수이다.
내부에 int를 감싸고 있으며, int 값은 힙 메모리(Heap)에 할당하고 있고 그게 대한 참조값(0x0080)을 가지고 있다.
하지만 int는 기본형 변수라서 참조값이 아닌, 참조하고 있는 값 자체가 필요하기 때문에
Integer에서 int로 변경하는데 비용이 필요하다는 것이다.
Integer를 Integer로 넣는 과정이나, int를 int로 넣는 과정에는 단지 복사만 해주면 되기 때문에 훨씬 빠르다.
참조형과 기본형을 어떻게 사용할 것이냐에 대한 고민도 하나의 과제인거 같다.. 😢🫠
