[프로그래머스] 두 개 뽑아서 더하기 - java

https://school.programmers.co.kr/learn/courses/30/lessons/68644

프로그래머스

문제 설명

단순히 각 원소를 더해 중복값 없이 오름차순 하는 문제이다. 처음 든 생각은 책에서 본 TreeSet을 적용하면 중복값 제거와 정렬을 동시에 할 수 있을 것이라고 생각을 하여 자료구조는 TreeSet을 사용하였다.

 

자료구조 설명은 지피티 쌤에게 물어봤다.

Set 인터페이스

Set 인터페이스는 중복된 요소를 허용하지 않는 컬렉션을 나타냅니다. 즉, 동일한 값을 가진 객체를 두 개 이상 가질 수 없습니다. 주요 메서드는 다음과 같습니다:

• add(E e): 지정된 요소를 집합에 추가합니다. 요소가 이미 존재하면 변경되지 않습니다.
• remove(Object o): 지정된 요소를 집합에서 제거합니다.
• contains(Object o): 지정된 요소가 집합에 있는지 여부를 확인합니다.
• size(): 집합의 요소 개수를 반환합니다.
• clear(): 모든 요소를 집합에서 제거합니다.
• isEmpty(): 집합이 비어 있는지 여부를 확인합니다.
• iterator(): 집합의 요소에 대한 반복자를 반환합니다.

TreeSet 클래스

TreeSet 클래스는 Set 인터페이스를 구현하며, 요소를 자연 순서(오름차순) 또는 생성 시 지정된 Comparator에 따라 정렬하는 정렬된 집합을 제공합니다. TreeSet은 이진 검색 트리인 레드-블랙 트리를 기반으로 하며, 주요 특징은 다음과 같습니다:

• 정렬: 요소는 자동으로 정렬됩니다.
• 범위 조회: 특정 범위의 요소를 쉽게 검색할 수 있습니다.
• 성능: 기본 연산(add, remove, contains 등)에 대해 O(log n)의 시간 복잡도를 가집니다.

주요 메서드는 Set 인터페이스의 메서드를 상속받으며, 추가적으로 NavigableSet 인터페이스의 메서드도 제공합니다:

• first(): 첫 번째(가장 낮은) 요소를 반환합니다.
• last(): 마지막(가장 높은) 요소를 반환합니다.
• headSet(E toElement): 지정된 요소보다 작은 모든 요소를 포함하는 집합을 반환합니다.
• tailSet(E fromElement): 지정된 요소보다 크거나 같은 모든 요소를 포함하는 집합을 반환합니다.
• subSet(E fromElement, E toElement): 지정된 범위 내의 모든 요소를 포함하는 집합을 반환합니다.

이러한 특징을 살렸고 참고로 내림차순으로 정렬을 하기 위해선

TreeSet<Integer> set = new TreeSet<>(Collections.reverseOrders());

 

를 사용하면 된다.

 

전부 TreeSet에 저장 후 배열 생성 후 값을 pollFirst로 옮긴 후 반환해준다.

 

참고

offerFirst() / offerLast() 

각각 앞, 뒤에 값을 넣는다.

pollFirst() / pollLast() 

각각 앞, 뒤의 값을 꺼냄

peekFirst() / peekLast()

각각 다음에 꺼낼 앞, 뒤의 값을 조회

 

코드

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

 

완성