프로그래머스 level1 두 개 뽑아서 더하기

문제 정의

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

제한사항은 numbers의 길이는 2 이상 100 이하이고, numbers의 모든 수는 0 이상 100 이하입니다.

 

 

 

문제 풀이 방향성

=> 월간 코드 챌린지 문제로, solution이라는 함수는 인자로 int형 벡터 numbers를 받고 int형 벡터를 반환할 데이터 타입으로 가진다. 그렇다 보니 헤더파일에 vector를 포함되어 있다. 입출력 예시를 보면 오름차순으로 정렬되어 출력이 되어야 하기 때문에 정렬 과정이 필요하다.

따로 정렬 알고리즘을 짜서 정렬해줘도 되는데, 코딩 테스트를 볼 때 이러한 부분에서 점수여부가 있는 경우도 있다고 들었지만 altorithm 헤더를 추가해서 sort 함수를 써서 정렬하는 방법으로 풀면서 급할 때 사용하는 방법을 익히고자 했다. 

 

sort함수는 다른 지정을 하지 않으면 디폴트로 오름차순이고(ASC), intro sort (인트로 정렬)라는 알고리즘을 이용한다.

인트로 정렬이 무엇인지 찾아보니 heap sort와 insertion sort를 혼합해서 만들었고 최악의 경우 시간복잡도는 nlogn이라고 한다. 종종 STL을 쓰지 말고 문제를 풀라는 문제가 있는데 그 경우를 제외하면 STL을 그래도 좀 알면 단축이라도 하니까 빠르게 문제를 풀 수 있어서 기억하고자 했다.

 

erease라는 벡터 내장 함수와 unique 사용해서 answer 벡터 내 중복 원소를 제거했다. 

unique함수는 중복되지 않는 원소들을 앞에서부터 채워나가는 역할을 하기때문에 남은 뒷부분은 그대로 vector 원소값이 존재한다.

즉 1 2 3 4 4 5 5 6 이 있다면 unique를 쓰면 1, 2, 3, 4, 5, 6이 되는게 아니라 1, 2, 3, 4, 5, 6, 4, 5 이렇게 된다는 것이다.

unique함수의 반환값으로 중복 제거 후 밀리게 된 원소 첫 번째 주소를 반환하기 때문에, 위의 예시에서는 7번째 자리인 4의 주소값을 반환하게 된다.

그래서 erase함수를 써서 unique에서 반환된 주소부터 answer.end()까지 걸어서 중복된 원소들 뒷부분을 지우고

중복되지 않은 원소들을 출력하는 것으로 했다.

 

 

 

소스 코드

#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;
}