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

 

나는 이 문제를 보고 예전 확률과 통계 같은 곳에서 풀던 문제들이 생각났다.

인덱스의 위치를 [0], [1] 이런식으로 표현해보겠다.

 

크기가 5인 배열이라고 가정해보면

[0] + [1], [0] + [2], [0] + [3], [0] + [4]

[1] + [2], [1] + [3], [1] + [4]

[2] + [3], [2] + [4]

[3] + [4]

 

이런식의 흐름을 떠올렸다.

 

이 생각을 기반으로 작성한 내 최종 코드다.

크기가 정해진 배열이 아니므로 ArrayList를 사용했고 앞서 설명한 방식으로 더하기 위해 이중 for문을 사용했다.

이후 문제 요구사항에 맞게 정렬을 했고 return 하기 위한 배열을 새로 만들어 list에 있는 값들을 넣음으로써 로직을 완성했다.

 

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        List<Integer> list = new ArrayList<>();
        
        for (int i=0; i<numbers.length-1; i++) {
            int sum = 0;
            
            for (int j=i+1; j<numbers.length; j++) {
                sum = numbers[i] + numbers[j];
                
                if (!list.contains(sum)) {
                    list.add(sum);
                }
            }
        }
        
        Collections.sort(list);
        
        int[] arr = new int[list.size()];
        
        for (int i=0; i<list.size(); i++) {
            arr[i] = list.get(i);       
        }
        
        return arr;
    }
}

 

 

나는 난이도와 상관없이 문제를 풀고 나서 찝찝한 느낌이 들면 언제나 gpt를 활용하여 최적화된 방법을 찾아본다.

이 과정에서 `HashSet`의 활용에 대해 알게 되었다.

아직 코딩테스트 경험이 적은 나에게는 생소한 것이었기에 기회 삼아 HashSet에 대한 것을 정리해보려고 한다.

 

HashSet이란?

중복을 허용하지 않는 집합(Set)

 

 

List

List<Integer> list = new ArrayList<>();

list.add(1);
list.add(1);
list.add(2);

 

결과:

[1, 1, 2]

중복이 허용된다.

 

HashSet

Set<Integer> set = new HashSet<>();

set.add(1);
set.add(1);
set.add(2);

 

결과:

[1, 2]

중복이 허용되지 않는다.

 

왜 HashSet이 빠른가?

if (!list.contains(sum)) {
    list.add(sum);
}

contains()는 앞에서부터 하나씩 검사한다.

 

예를 들어:

[3, 4, 5, 6, 7]

에서 7을 찾으려면

3 확인
4 확인
5 확인
6 확인
7 확인

최악의 경우 전부 검사한다.

 

반면 HashSet은

set.contains(7);

을 거의 즉시 찾는다.

내부적으로 해시(Hash) 를 사용하기 때문이다.

 

HashSet을 사용한 코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {

        Set<Integer> set = new HashSet<>();

        for (int i = 0; i < numbers.length - 1; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                set.add(numbers[i] + numbers[j]);
            }
        }

        List<Integer> list = new ArrayList<>(set);

        Collections.sort(list);

        int[] answer = new int[list.size()];

        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }

        return answer;
    }
}