Lv1_[삼총사, C++] 풀이 및 알고리즘 정리 - 프로그래머스

 

프로그래머스

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

---

알고리즘

풀이 방식의 핵심은 3명을 뽑은 경우의 수를 뽑는 것!

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

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

 

3개의 수만 뽑으면 되기 때문에 조합(next_permutation, prev_permutation)을 사용과 삼중 반복문을 이용해서 조합 뽑는 두가지 방법을 코드로 구성해놨다.
(※ 뽑아야하는 개수가 커지면 반복문 보다는 조합(next_permutation, prev_permutation)을 사용하는 것이 유리함)

위의 방법으로 3명을 뽑았다면 모두 더했을 때, 0이 되는 경우의 수만 카운트해주면 삼총사를 만들 수 있는 방법의 수가 리턴된다.

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int solution(vector<int> number) {
    int answer = 0;
 
#if 1    // 조합
    sort(number.begin(), number.end());
    vector<int> tmp(number.size(), 0);
    tmp[0] = 1;
    tmp[1] = 1;
    tmp[2] = 1;
 
    do {
        int num = 0;
        for(int i = 0; i < tmp.size(); i++) {
            if(tmp[i] == 1) {
                num += number[i];
            }
        }
        if(num == 0) {
            answer++;
        }
    } while(prev_permutation(tmp.begin(), tmp.end()));
 
#else    // 삼중 반복문
    for(unsigned int i = 0; i < number.size() - 2; i++) {
        for(unsigned int k = i+1; k < number.size() - 1; k++) {
            for(unsigned int p = k+1; p < number.size(); p++) {
                int sum = number[i] + number[k] + number[p];
                if(sum == 0) {
                    answer++;
                }
            }
        }
    }
#endif
 
    return answer;
}

 

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