프로그래머스_두 개 뽑아서 더하기 JAVA

프로그래머스

 

이번에 풀 문제는 '두 개 뽑아서 더하기'다.

과거에 풀었던 문제라 과거 코드가 남아있다.

근데 진짜 푼 기억이 없는데 도대체 뭐지;;

대충 풀고 베꼈을ㄲ..ㅏ?

 

과거 코드

import java.util.*;
class Solution {
    public TreeSet<Integer> solution(int[] numbers) {
        TreeSet<Integer> answer = new TreeSet<>();
        
        for(int i = 0; i < numbers.length; i++) {
            for(int j = i+1; j < numbers.length; j++) {
                answer.add(numbers[i] + numbers[j]);
            }
        }
        
        return answer;
    }
}

과거에는  TreeSet의 자료구조로 문제를 풀었다.

 

현재 코드 - 중간

import java.util.*;
class Solution {
    public Set<Integer> solution(int[] numbers) {
        Set<Integer> answer = new HashSet<>();;
        
        for(int i = 0; i < numbers.length; i++) {
            for (int j = i+1; j <numbers.length; j++) {
                answer.add(numbers[j] + numbers[i]);
            }
        }
        
        return answer;
    }
}

익숙한 Set으로 해서 제출했다가... TreeSet을 사용한 이유를 알게됐다.

Set은 정렬이 안돼서 이중 for문 이후에 따로 정렬 코드를 추가해줘야한다.

 

현재 코드 = 과거 코드

import java.util.*;
class Solution {
    public TreeSet<Integer> solution(int[] numbers) {
        TreeSet<Integer> answer = new TreeSet<>();;
        
        for(int i = 0; i < numbers.length; i++) {
            for (int j = i+1; j <numbers.length; j++) {
                answer.add(numbers[j] + numbers[i]);
            }
        }
        
        return answer;
    }
}

 

TreeSet

특징

• 자동 정렬 : 데이터를 넣을 때 오름차순으로 정렬해줌
• 중복 허용 X : Set과 동일
• 빠른 검색 : 이진 탐색 트리 구조 덕분에 데이터 검색, 추가, 삭제 속도 가 빠름

 

자동 정렬이 되는 이유는 이진 탐색 트리 구조라 그런데 이 노드의 정렬 규칙은 아래와 같다.

1. 각 노드는 왼쪽 자식과 오른쪽 자식을 가진다.

2. 왼쪽 자식 노드의 값은 부모 노드보다 작다.

3. 오른쪽 자식 노드의 값은 부모 노드보다 크다.

 

탐색 또한 정렬이 되어있어 값 비교를 통해 한 방향으로만 이동하므로 시간 복잡도가 O(log n) 수준이다.

 

중복을 제거해주면서 정렬까지 해주는 TreeSet  잊지말자~!

 

오늘도 즐,거운,코딩