[코딩테스트합격자되기-자바편] 문제03. 두 개 뽑아서 더하기

💡 해당 풀이는 코딩 테스트 합격자되기 - 자바편 에서 발췌된 내용을 바탕으로 작성되었습니다.

 

문제

내용

정수 배열 numbers 가 주어집니다. numbers에서 서로 다른 인덱스에 있는 2개의 수를 뽑아 더해 만들 수 있는 모든 수를 배열에 오름차순으로 담아 반환하는 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]

 

기록하기

💡 어디까지 생각해봤는지 단계적으로 기록해봅니다.

 

1. 중첩 반복문으로 numbers에서 서로 다른 인덱스에 있는 2개의 수를 더한 값들을 정수형 배열에 담는다.
2. 중복값을 제거한다.

 

 

풀이

풀이 시간

 

시작 시각	종료 시각	총 소요 시간
17:40	17:49	9분

 

 

문제 분석

제약 사항 파악 & 테스트 케이스 작성

• 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]

 

 

의사 코드 작성

💡 의사 코드는 동작 중심으로 작성하는 것이 중요합니다.

💡 의사 코드는 문제 해결 순서로 작성합니다.

💡 의사 코드를 충분히 테스트해봅니다.

solution(int[] numbers) {
    result = 정수형 ArrayList
    for (i = 0; numbers 길이미만) {
        for (j = 0; numbers 길이 미만) {
            if (i != j) {
                // result 에 두 수를 더한 값 추가
            }
        }
    }

    // result 중복제거
    // result 오름차순 정렬
    return result
}

 

 

구현

import java.util.ArrayList;  
import java.util.Arrays;  
import java.util.List;

public static int[] solution(int[] numbers) {  
    List<Integer> result = new ArrayList<>();  
    for (int i = 0; i < numbers.length; i++) {  
        for (int j = 0; j < numbers.length; j++) {  
            if (i != j) {  
                // result 에 두 수를 더한 값 추가  
                result.add(numbers[i] + numbers[j]);  
            }  
        }  
    }  

    // result 중복제거 후 오름차순 정렬  
    return result.stream()  
            .distinct()  
            .sorted()  
            .mapToInt(Integer::intValue)  
            .toArray();  
}

 

 

복기하기

답안과 나의 풀이를 비교해보세요

저자 권장시간	권장 시간 복잡도
30분	O(N^2log(N^2))

import java.util.HashSet

class Solution {
    public int[] solution(int[] numbers) {
        // 중복값 제거를 위한 해시셋 생성
        HashSet<Integer> result = new HashSet<Integer>();
        // 두 수를 선택하는 모든 경우의 수를 반복문으로 구함
        for (int i = 0; i < numbers.length - 1; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                // 두 수를 더한 결과를 해시셋에 추가
                result.add(numbers[i] + numbers[j]);
            }
        }
        // 해시셋의 값을 오름차순 정렬하고 int[] 형태의 배열로 반환
        return result.stream().sorted().mapToInt(Integer::intValue).toArray();
    }
}

• i와 j의 시작점을 다르게 해서 중복 계산이 제거되어 성능이 향상된다.
• 해시셋을 사용하여 중복값을 제거한다.

 

요약하기

• 이중 반복문을 통해 모든 원소들에 대한 두 수의 합을 구하는 연산의 시간 복잡도는 O(N^2)
• Set으로 만들 때 시간 복잡도는 O(N^2)이고 N^2개의 데이털르 정렬하는 데는 O(N^2log(N^2))