[PCCP] Lv1: 두 개 뽑아서 더하기(68644)

문제

- 링크: 두 개 뽑아서 더하기(Lv1)

- 문제

(문제설명)

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

2) 과정 1에서 구한 수를 새로운 배열에 저장하고 중복값을 제거

3) 배열을 오름차순으로 정렬하고 반환

 

코드

(C언어) 

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

// numbers_len은 배열 numbers의 길이입니다.
int* solution(int numbers[], size_t numbers_len) {
    // return 값은 malloc 등 동적 할당을 사용해주세요. 할당 길이는 상황에 맞게 변경해주세요.
    int* answer = (int*)malloc(sizeof(int));
    return answer;
}

 

(C++)

solution 1)

- numbers의 길이 N

- 이중 반복문으로 모든 원소에 대해 두 수의 합 구하기: O(N^2)

- set으로 변환: O(N^2)

- N^2개의 데이터를 insert()하는 경우: O(N^2 * log(N)) 

- 최종 시간 복잡도: O(N^2 * logN)

#include <set>
#include <vector>

using namespace std;

vector<int> solution(vector<int> numbers) {
    set<int> sum;  // 두 수의 합 저장 공간
    
    // 반복문을 수행하며 두 수의 합 저장
    for (int i = 0; i < numbers.size(); ++i) {
        for (int j = i + 1; j < numbers.size(); ++j) {
            sum.insert(numbers[i] + numbers[j]);
        }
    }
    
    vector<int> answer(sum.begin(), sum.end());
    
    return answer;
}

solution 2)

- set 활용

#include <string>
#include <vector>
#include <set>

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer;
    set<int> result;
    for (int i = 0; i < numbers.size(); ++i) {
        for (int j = i+1; j < numbers.size(); ++j) {
            result.insert(numbers[i]+numbers[j]);
        }
    }
    
    answer.assign(result.begin(), result.end());
    
    return answer;
}

solution 3)

- 배열과 정렬 활용. 중복 제거

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer;
    for (int i = 0; i < numbers.size(); ++i) {
        for (int j = i+1; j < numbers.size(); ++j) {
            answer.push_back(numbers[i]+numbers[j]);
        }
    }
    
    sort(answer.begin(), answer.end());
    answer.erase(unique(answer.begin(), answer.end()), answer.end());
    
    return answer;
}

 

(C#)

using System;

public class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[] {};
        return answer;
    }
}

 

(Java)

solution1) 

- N: numbers의 길이

- 이중 반복문을 통해 모든 원소들에 대한 두 수의 합을 구하는 연산의 시간 복잡도: O(N^2)

- 이후 이를 Set으로 만들 때 시간 복잡도: O(N^2)

- N^2개의 데이터를 정렬하는데는 O((N^2)*log(N^2))

- 최종 시간 복잡도: O((N^2)*log(N^2))

import java.util.HashSet;

class Solution {
    public int[] solution(int[] numbers) {
        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]);
            }
        }
        
        // 해시셋의 값을 오름차순 정렬하고 int[] 형태의 배열로 변환하여 반환
        return set.stream().sorted().mapToInt(Integer::intValue).toArray();
    }
}

 

solution2) 

d

solution3) 

d

 

 

(Python)

solution1)

- N: numbers의 길이

- 모든 조합 확인: O(N^2)

- 모든 조합을 정렬: O(N^2 * log(N^2))

- 최종시간복잡도: O(N^2 * log(N^2))

def solution(numbers):
    ret = [] # 빈 배열 생성
    # 두 수를 선택하는 모든 경우의 수를 반복문으로 구함
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            # 두 수를 더한 결과를 새로운 배열에 추가
            ret.append(numbers[i] + numbers[j])
    # 중복된 값을 제거하고, 오름차순으로 정렬
    ret = sorted(set(ret))
    return ret # 최종 결과 반환

solution2) 

def solution(numbers):
    answer = []
    for i in range(len(numbers)):
        for j in range(i+1, len(numbers)):
            answer.append(numbers[i] + numbers[j])
    answer = list(set(answer))
    return sorted(answer)

solution3)

  

(JavaScript)

solution1) 

- N: numbers의 길이

- 모든 조합 확인: O(N^2)

- 모든 조합을 정렬: O(N^2 * log(N^2))

- 최종시간복잡도: O(N^2 * log(N^2))

function solution(numbers) {
    const ret = [];  // 빈 배열 생성
    
    // 두 수를 선택하는 모든 경우의 수를 반복문으로 처리
    for (let i = 0; i < numbers.length; ++i) {
        for (let j = 0; j < i; ++j) {
            // 두 수를 더한 결과를 새로운 배열에 추가
            ret.push(numbers[i] + numbers[j]);
        }
    }
    // 중복된 값으 제거하고, 오름 차순으로 정렬 후 반환
    return [...new Set(ret)].sort((a, b) => a - b);
}

solution2)

d