Lv1_[두 개 뽑아서 더하기, C++] 풀이 및 알고리즘 정리 - 프로그래머스

 

프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

알고리즘

풀이 방식의 핵심은 두 개의 수를 뽑는 것!

 

그러면 떠오르는 방법은 두가지

1. 배열 s의 n개의 원소 중에서 r개의 원소를 택하는 방법 (조합을 구하는 방법)
2. 반복문을 이용해서 모든 조합 뽑기

여기서는 두 개의 수만 뽑으면 되기 때문에 조합(next_permutation, prev_permutation)을 사용해도 되지만 이중 반복문을 이용해서 조합을 뽑았다(※ 뽑아야하는 개수가 커지면 반복문 보다는 조합(next_permutation, prev_permutation)을 사용하는 것이 유리함)

 

두 개의 수를 뽑아서 더했을 때 중복된 값을 존재할 수 있으므로 저장되는 자료구조는 set을 사용해서 중복을 없애는 방법을 사용오름차순으로 정렬을 해야하기 때문에 "set<int>" or "set<int, less<int>>" 로 선언 (set 기본이 오름차순이기 때문에 less<int>는 생략해도 됨)

그리고 set을 vector로 저장해주면서 리턴해주면 완료!

 

#include <vector>
#include <set>
 
using namespace std;
 
vector<int> solution(vector<int> numbers)
{
    set<int, less<int>> s;
    
    for (int i = 0; i < numbers.size() - 1; i++) {
        for (int k = i + 1; k < numbers.size(); k++) {
            int sum = numbers[i] + numbers[k];
            s.insert(sum);
        }
    }
 
    return vector<int>(s.begin(), s.end());
}

결과 시간

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓