[프로그래머스 / C++] 삼총사

문제

삼총사 : 문제 링크

문제 분석

• 한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 한다. 예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사이다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사이다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있다. 한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성

• 제한 사항

• 3 <= number의 길이 <= 13
• -1,000 <= number의 각 원소 <= 1,000
• 서로 다른 학생의 정수 번호가 같을 수 있다.

• 조합을 구현하기 위해 next_permutation() 함수를 사용해야 하므로 algorithm 헤더를 include
• 삼총사를 만들 있는 방법의 수를 저장할 정수형 변수 answer을 0으로, 조합을 구하기 위해 활용할 정수형 벡터 visit을 초기화. 이 문제는 조합(nCr)을 구현하여 풀어야하는 문제이므로 보조 수열(전체의 길이가 n, 1의 개수가 r, 나머지가 0으로 채워진(1은 뒤에서 부터 채워야 함))을 생성해야 함. 따라서 for loop 두 개를 활용하여, 정수형 벡터 visit의 number.size() - 3 미만의 인덱스 까지는 0을, 이후의 인덱스는 1로 저장
• 이후 do ~ while문을 활용하고, next_permutation() 함수를 사용하여 보조 수열에 대한 모든 조합의 케이스를 만든다. 각 조합의 합을 저장할 정수형 변수 sum을 0으로 초기화하고, loop내에 for loop를 number의 첫번째부터 마지막 원소까지 순환. if문을 사용하여 현재 보조 수열의 원소가 1이라면, 즉 조합의 경우라면 sum에 number의 원소를 sum에 더하고 저장. loop 탈출 후, 또다른 if문을 사용하여 sum이 0이라면 조건을 만족하므로 answer을 1씩 늘림. 모든 do ~ while loop 탈출 후, 최종적으로 저장된 answer을 return

algorithm 헤더의 next_permutation() 함수 사용법
bool next_permutation (BidirectionalInterator first, BidirectionalIterator last);

• 순열을 구할 1)시작과 끝의 iterator 혹은 배열의 경우 2)시작과 끝의 주소를 입력받음
• 현재 탐색하고 있는 순열의 다음 순열을 구하고 true를 return하고, 다음 순열이 존재하지 않는다면 false를 return

풀이

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> number) {
    int answer = 0;
    vector<int> visit;
    
    for(int i = 0; i < number.size() - 3; ++i) visit.push_back(0);
    for(int i = number.size() - 3; i < number.size(); ++i) visit.push_back(1);
    do {
        int sum = 0;
        for(int i = 0; i < number.size(); ++i) {
            if(visit[i] == 1) sum += number[i];
        }
        if(sum == 0) answer++;
    } while(next_permutation(visit.begin(), visit.end()));
    
    return answer;
}