[201105] 두 개 뽑아서 더하기 - 월간 코드 챌린지 시즌1(level1)

0. 문제 유형 : 반복문의 적절한 활용, (하위 버전의) 완전 탐색

1. 문제 이해

programmers.co.kr/learn/courses/30/lessons/68644

코딩테스트 연습 - 두 개 뽑아서 더하기

(1) 주요 요구사항 : 주어진 정수 배열 numbers에서 서로 다른 인덱스의 두 수를 뽑아 더해서 만들 수 있는 모든 수

(2) 추가 조건 : 배열에 오름차순으로 담아 return

 

 

2. 전략

(1) 두 개의 수를 뽑아 더하기

- 모든 경우의 두 수에 대해 수행해야 되므로 완전탐색이 필요

- 중첩 for문 이용 : 0~numbers.length-1까지 각 인덱스와 뒤따라오는 인덱스에 대해서 덧셈 수행

 

(2) 두 수를 더한 경우가 중복이 될 가능성

- 예제> [2, 1, 3, 4, 1]인 경우 2+3, 1+4의 경우 5로 같은 값이 나옴

  BUT 결과 배열에는 중복이 없어야

- HashSet의 특성을 이용 : Set 컬렉션은 중복과 순서가 없음

  → 덧셈의 결과를 HashSet에 담는다.

 

(3) 배열에 오름차순으로 담아 return

- HashSet을 배열에 담는 방법

: Set 컬렉션에는 List와 Map의 get 메소드처럼 index를 통한 접근이 불가능. 다음 2가지 방식으로 object에 순차적 접근 가능

//(방법1) 개선된 for문
answer = new int[set.size()]; int index = 0;
for(int s : set)	answer[index++] = s;

//(방법2) Iterator
answer = new int[set.size()]; int index = 0;
Iterator<Integer> iter = set.iterator();
while(iter.hasNext())	answer[index++] = iter.next();

- 컬렉션의 object를 오름차순 정렬 후 배열에 담기 VS 배열에 담은 후 오름차순 정렬하기

   →  Set은 순서가 없기 때문에 Collections.sort를 이용해 정렬하는 것이 불가능하다. 배열에 담은 후 Arrays.sort를 이용해 쉽게 오름차순 정렬할 수 있다.

 

 

3. 참고사항

(1) java8 스트림 활용 : HashSet을 배열에 오름차순으로 담는 과정 간단화

- 스트림 동작 흐름 : 스트림 생성 - 중개 연산(스트림 변환) - 최종 연산(스트림 사용)

생성 : HashSet을 stream으로 생성해야 됨 → stream

중개 연산 : 오름차순으로 정렬해야 됨 → sorted

최종 연산 : int 배열로 변환(Collectors의 수집 메소드 활용) → mapToInt(Integer::intValue).toArray()▶ set.stream().sorted().mapToInt(Integer.intValue).toArray();

 

(2) 시간복잡도

- 중첩 for문 : n + (n-1) + (n-2) + ... + 2 + 1 => O(n^2)

- Arrays.sort : Dual-Pivot Quick Sort를 이용 => O(nlogn)

▶ 시간복잡도 = O(n^2)

 

 

4. 코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = {};
        HashSet<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]);
            }
        }
        //Set은 순서가 없으므로 sort할 수 없다는 사실!! + set에서 배열로?
        answer = new int[set.size()];
        int index = 0;
        for(int s : set)    answer[index++] = s;
        //sort
        Arrays.sort(answer);
        return answer;
    }
}