[프로그래머스/C++] 두 개 뽑아서 더하기 (Lv.1)

링크: https://school.programmers.co.kr/learn/courses/30/lessons/68644?language=cpp

프로그래머스

 

1. 문제 접근

이 문제는 numbers 배열에서 서로 다른 인덱스에 있는 두 수를 뽑아 더한 뒤, 만들 수 있는 모든 합을 오름차순으로 반환하는 문제이다.

핵심 조건은 두 가지이다.

1. 같은 원소를 두 번 사용할 수 없다.
2. 결과값은 중복 없이 오름차순이어야 한다.

따라서 이중 반복문을 사용해 i번째 원소와 j번째 원소를 더한다. 이때 j = i + 1부터 시작하면 같은 원소를 더하는 경우를 피할 수 있다.

그리고 중복 제거와 정렬은 set을 사용하면 쉽게 처리할 수 있다. set은 값을 자동으로 오름차순 정렬하며, 중복된 값은 저장하지 않기 때문이다. ⇒ 핵심 idea

 

 

2. 풀이 (2개)

• 1번 코드
  

  #include <string>
  #include <vector>
  #include <set>
  #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++){
              int a = numbers[i] + numbers[j];
              answer.push_back(a);
          }
      }
  
      set<int> s(answer.begin(), answer.end()); // 중복제거+오름차순
      vector<int> answers(s.begin(), s.end()); // set->vector 변환
  
      return answers;
  }
  ​

  - 이 코드는 먼저 가능한 모든 두 수의 합을 answer 벡터에 저장한다.
  
  
• 2번 코드
  

  #include <string>
  #include <vector>
  #include <algorithm>
  #include <set>
  
  using namespace std;
  
  vector<int> solution(vector<int> numbers) {
      vector<int> answer;
      set<int> st;
  
      for(int i = 0; i < numbers.size(); ++i){
          for(int j = i + 1; j < numbers.size(); ++j){
              st.insert(numbers[i] + numbers[j]); // set에 삽입
          }
      }
      // assign()함수 사용해서 set 값을 answer 벡터에 복사
      answer.assign(st.begin(), st.end());
      return answer;
  }
  ​

   - 이 코드는 처음부터 합계를 vector가 아니라 set에 바로 저장한다.

 

3. 문법 설명

• set
  

  set<int> st;

   - C++ STL 컨테이너(C++에서 데이터를 담아두는 기본 자료구조 도구) 중 하나로, 다음과 같은 특징이 있다.
  1. 중복 값을 허용하지 않는다.
  2. 값을 자동으로 오름차순 정렬한다.
  3. 값을 삽입할 때 insert()를 사용한다.
  예를 들어 다음과 같이 값을 넣으면,
  

  set<int> st;
  
  st.insert(3);
  st.insert(1);
  st.insert(2);
  st.insert(3);
  
  //실제로 저장되는 값은 다음과 같다.
  1 2 3
  3을 두 번 넣었지만 set은 중복을 허용하지 않기 때문에 한 번만 저장된다.

  
  
  
• insert 함수
  insert()는 값을 삽입할 때 사용하는 함수이다. (컨테이너 종류에 따라 사용 방식 다름)
  

  // 일반적 형태
  set이름.insert(값);
  
  st.insert(numbers[i] + numbers[j]);

  
  
  
• assign 함수
  assign()은 기존 벡터의 내용을 지우고, 새로운 범위의 값으로 다시 채우는 함수이다.
  

  // 일반적 형태
  vector이름.assign(시작반복자, 끝반복자);
  
  answer.assign(st.begin(), st.end());

  
  즉, 아래 코드와 비슷한 의미이다.
  

  vector<int> answer(st.begin(), st.end());
  
  // 차이점은 아래와 같다.
  vector<int> answer(st.begin(), st.end()); - 벡터 새롭게 만들면서 값 넣는 방식
  answer.assign(st.begin(), st.end()); - 이미 만들어진 벡터 값 다시 채우는 방식

  
  
  
• vector 생성자 방식(vector를 만들 때부터 값을 넣어서 생성하는 방식)

  // 1번 코드에서 사용한 방식
  vector<int> answers(s.begin(), s.end());
  
  이 코드는 `set`의 시작부터 끝까지 값을 가져와서 새로운 벡터 `answers`를 만든다는 뜻이다.
  
  즉, `set`을 `vector`로 변환 목적

 

4. 최종 요약

이 문제는 모든 두 수의 합을 구한 뒤, 중복 제거와 오름차순 정렬을 하면 된다.set은 중복 제거와 정렬을 자동으로 처리해주기 때문에 이 문제에 적합하다.

1번 풀이는 모든 합을 먼저 vector에 저장한 뒤 set으로 변환하고 다시 vector로 변환.

2번 풀이는 처음부터 set에 합을 저장하는 방식이므로 더 깔끔하다.