[알고리즘] 두 개 뽑아서 더하기: Set 인터페이스 활용

문제 요구사항

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• numbers의 길이는 2 이상 100 이하입니다.
  • numbers의 모든 수는 0 이상 100 이하입니다.

 

3줄 접근

서로 다른 인덱스에 있는 모든 두 수를 더하고, 순서를 보장해 주는 Treeset에 더한다.
set에 담긴 요소들을 배열에 복사한다.
배열을 출력한다.

나의 풀이

import java.util.Set;
import java.util.TreeSet;

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

정답 확인 전 실수 요인

1. 순회자 j의 값을 j = 1이 아닌 j = i + 1로 초기화했어야 했다. 배열 안에서 서로 다른 두 수의 합을 구하는 것이기 때문이다. 
2. 순회자 i의 경계값을 numbers.length - 1로 했어야 했다. j가 끝까지 가기 때문이다. 

 

모범답안

import java.util.HashSet;
import java.util.Set;

class Solution {
     public int[] solution(int[] numbers) {
        Set<Integer> set = new HashSet<>();

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

        return set.stream().sorted().mapToInt(Integer::intValue).toArray();
    }
}

잘한 점

• TreeSet 사용 대신 시간복잡도가 낮은 HashSet 사용 후 정렬하는 전략

아쉬운 점

• i의 경계값을 numbers.length - 1로 지정하지 않아 numbers의 마지막 요소끼리 더해진다. 예상치 못한 결과값을 초래할 수 있다는 점에서 매우 심각한 실수.

다른 답안

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;

class Solution {
    public static ArrayList<Integer> solution(int[] numbers) {
        ArrayList<Integer> answer = new ArrayList<>();
        HashSet<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]);
            }
        }

        Iterator<Integer> iter = set.iterator();
        while(iter.hasNext()) {
            answer.add(iter.next());
        }

        Collections.sort(answer);
        return answer;
    }
}

잘한 점

• i의 경계값을 numbers.length - 1로 설정하여 중복 덧셈 방지
• j의 초기값을 i+1로 설정하여 중복 덧셈 방지

아쉬운 점

• i의 경계값을 numbers.length - 1로 지정하지 않아 numbers의 마지막 요소끼리 더해진다. 예상치 못한 결과값을 초래할 수 있다는 점에서 매우 심각한 실수.
• 정수 배열로 반환하라는 조건을 임의로 변경했다.

인사이트

TreeSet을 사용하면 add와 동시에 정렬이 가능하지만,
트리 재배치 과정으로 인해 HashSet 대비 시간복잡도가 불리하다.
Iterator 사용법을 언제 왜 쓰는지 중심으로 공부하자.
java.util.Set은 java.util.TreeSet과 다르다. 
프로그래머스에서는 return 타입을 바꿔도 된다.

Github 링크

[level 1] Title: 두 개 뽑아서 더하기, Time: 6.21 ms, Memory: 88.6 MB -Baekjoo… · ginsengcandy/Coding-Test-Practice@e4

 

문제 출처

프로그래머스

 

References

Set (Java Platform SE 8 )

 

W3Schools.com