문제링크

문제 이해

[ 입력형태 / 조건 ]

numbers
정수 배열 | [2,1,3,4,1]

[ 문제 ]

=> numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return

[ 풀이 ]

중복이 없어야 하므로 Set에 넣고, 이를 int[]배열로 변환한 뒤 정렬하여 출력

---

코드

> [성공] 1차 시도 : Set + Arrays.sort()

• 생각한 풀이 그대로 구현

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        Set<Integer> possi_nums = new HashSet<>();
        for(int i=0; i<numbers.length; i++){
            for(int j=i+1; j<numbers.length; j++){
                possi_nums.add(numbers[i]+numbers[j]);
            }
        }
        
        int[] answer = possi_nums.stream().mapToInt(Integer::intValue).toArray();
        Arrays.sort(answer);
        return answer;
    }
}

=> Set을 int[]로 치환하는 것과 정렬에 많은 시간이 소요될 것이라 생각했고 실제 실행속도도 느렸음

> [성공] 2차 시도 : PriorityQueue + boolean[]

• numbers[]에서 가능한 합을 인덱스로 하는 boolean[]의 값을 true로 둠
• 이를 설정하기 위해선 boolean[]의 크기를 설정해야하는데, PriorityQueue로 최댓값 2개를 추출하여 해당 합을 최대 인덱스로 설정
• 일부를 true로 바꿔둔 boolean[]의 처음부터 true인 부분을 체크하고 추가하면 오름차순 정렬을 따로 할 필요가 없음

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for(int node : numbers){
             pq.add(node);
         }
        
        int cnt = 0;
        boolean[] possi_nums = new boolean[pq.poll()+pq.poll()+1];
        for(int i=0; i<numbers.length; i++){
            for(int j=i+1; j<numbers.length; j++){
                if(possi_nums[numbers[i]+numbers[j]])
                    continue;
                possi_nums[numbers[i]+numbers[j]] = true;
                cnt += 1;
            }
        }
        
        int[] answer = new int[cnt];
        int idx = 0;
        for(int i=0; i<possi_nums.length; i++){
            if(possi_nums[i]){
                answer[idx] = i;
                idx+=1;
            }
        }
        return answer;
    }
}

자료형 변환이나 정렬을 따로 하지 않아서 빠르게 실행 가능했음

TIP : 자료형간의 변환 방법은 알아둬야 한다