[알고리즘/Programmers] LV1. 두 개 뽑아서 더하기

Programmers LV1. 두 개 뽑아서 더하기

 

문제 설명

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

제한 사항

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

입출력 예

numbers	result
[2,1,3,4,1]	[2,3,4,5,6,7]
[5,0,2,7]	[2,5,7,9,12]

---

사용 언어

Java

해결 방법

로직을 위해 순차적으로 세 가지 지점을 파악했다.

1. 두 수를 탐색하고 두 수의 합이 list에 없으면 list에 추가

2. list -> 배열 변환

3. 오름차순 정렬

(2,3 순서는 바뀔 수 있다고 생각함)

컬렉션 자료구조 선택은 여러가지가 있겠지만 크게 두가지로 나뉜다.

1. ArrayList

• 장점 : 속도 더 빠름

2. TreeSet

• 장점 : add 시 순차정렬 알아서 됨

자료구조 -> 배열 변환 과정(2번) 때문에 코드량의 큰 차이가 없다.

속도면에서는 ArrayList, 문제 내용과 찰떡인건 TreeSet 이라고 판단된다.

알게된 것

• Collection 종류
  • ArrayList, TreeSet, HashSet 차이
• 자료구조 간 변환 문법
  • 배열 -> ArrayList : Arrays.asList(list);
  • ArrayList -> 배열 : 순회해서 각각 넣어주어야 한다. (또 다른 방법이 있을까요??)
• 순회 문법
  • for문
  • Iterator (List형 컬렉션이 아닌 경우 인덱스가 없으므로 Iterator로 순회)
  • lamda식 map (Set형도 가능한지 테스트 필요함)

코드

package programmers;

import java.util.*;

public class test_68644 {
    /*
     * 두 개 뽑아 더하기
     */

    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        int[] numbers = {2,1,3,4,1,2,5,7,3,1,4,2};
        //int[] numbers = {5,0,2,7};

        int[] result = solution2(numbers);

        for(int i=0; i<result.length; i++) {
            System.out.print(result[i] + ", ");
        }

        long end = System.currentTimeMillis();

        System.out.println( "실행 시간 : " + ( end - start )/1000.0 +"초"); //최종 실행시간

    }

    // ArrayList
    public static int[] solution(int[] numbers) {
        List<Integer> list = new ArrayList<>();

        for(int i=0; i<numbers.length; i++) {
            for(int j=i+1; j<numbers.length; j++) {
                // 두 수를 탐색
                // 두 수의 합이 list에 없으면 list에 추가
                int sum = numbers[i] + numbers[j];
                if(!list.contains(sum)) list.add(sum);
            }
        }
        // list to 배열 변환
        int[] answer = new int[list.size()];
        for(int i=0; i<list.size(); i++) {
            answer[i] = list.get(i);
        }
        // list 오름차순 정렬
        Arrays.sort(answer);

        return answer;
    }

    // TreeSet
    // 장점 : 정렬하면서 set에 추가된다. 중복은 무시된다.
    // 단점 : ArrayList 보다 실행 시간 느리다.
    public static int[] solution2(int[] numbers) {
        Set<Integer> list = new TreeSet<>();

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

        int[] result = new int[list.size()];
        int cnt = 0;

        Iterator<Integer> ir = list.iterator();
        while(ir.hasNext()) {
            result[cnt++] = ir.next();
        }

        return result;

    }

}