프로그래머스에서 푼 문제이다. 알고리즘 문제를 풀때마다 느끼는 거지만, 접근 방법은 다양한 것 같다.
난 보자마자 DFS로 풀어야 겠다라고 생각했고 풀었는데, 다른 분들 풀이를 보니 다양한 방법으로 푸셨다.
문제를 풀었다는 것 자체보다 왜 그런 결론에 도달 했는지, 왜 그렇게 생각했는지가 중요하므로 기록으로 남겨두려고 한다.
문제 풀이에 앞서 하고싶은 말을 간략하게 하고 시작 하려고 한다.
이 문제를 다 풀고 다른 사람의 풀이를 보는데 대부분 정답은 비슷했다.
만약 문제를 푸신 분이라면, 이 문제 만큼은 꼭 다른분들 풀이를 자세히 보길 바란다.
아마 보다보면 궁금증이 생길거라고 생각한다. 대부분의 풀이는 for문을 3중으로 사용하여 제출 되었다.
무엇이 문제냐? 라고 할 수도 있다. 그럼 이 글을 다 읽고 다시 풀이를 보는게 좋을 것 같다.
1. 소수 만들기
1.1 문제 소개
문제 설명
주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.
제한사항
- nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
- nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.
입출력 예
| nums | result |
|---|---|
| [1,2,3,4] | 1 |
| [1,2,7,6,4] | 4 |
입출력 예 설명
입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.
입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.
#include <vector>
#include <iostream>
using namespace std;
int solution(vector<int> nums) {
int answer = -1;
// [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
cout << "Hello Cpp" << endl;
return answer;
}
2. 문제 해결 과정
2.0. 제출 형식에 대한 이야기
백준의 경우는 입출력까지도 모두 코드를 작성해야 한다.
그런데 프로그래머스는 친절하게도 입출력은 고려하지 않아도 된다.
함수를 구현하고 정답을 리턴값으로 넘겨주면 채점을 해준다.
이게 왜 간편하냐면 백준 같은 경우에 문제를 다 풀고도 입출력 부분에 때문에 틀리는 경우도 있기 때문이다.
2.1. 문제 접근 방법
3개의 수를 더해서 소수가 되는 경우를 확인 하기 위해서는 결국 모든 경우의 수를 따져봐야한다.
포인트는 3개의 수이다. 3개 미만, 3개 이상인 경우는 소수인지 확인할 필요가 없다.
3개일때만 소수인지 확인하고 맞으면 소수가 되는 경우의 수를 증가 시켜주면 된다.
DFS 돌리면서 3개인경우만 신경 쓰면된다. (백트래킹)
2.2. DFS
3개의 경우의 수를 뽑는다고 했을때, 3개의 수를 더해야 하므로, 중복이 허용되는 조합이다.
즉 [1,3,5] 와 [3,1,5]는 같은 경우라고 봐야한다. 세수의 합이 같기 때문이다.
순차적으로 모든 경우의 수를 따져봐야하기 때문에
배열의 첫번째 숫자부터 그뒤의 나머지 숫자들을 더해가며, 더한 수가 3개일때 소수인지 확인하고
소수이면 소수가 되는 경우의수 를 증가시켜준다.
DFS 과정은 다음과 같을 것이다. 숫자는 배열의 번째라고 볼 수 있다.
1 -> 2 -> 3
1 -> 2 -> 4
1 -> 2 -> 5
1 -> 3 -> 4
1 -> 4 -> 5
이런식으로 확인 하게 될것이다.
2.3 문제 해결
2.4 백트래킹 (Back-tracking)
숫자 3개가 모인 경우에만 소수인지 확인하고 나머지 경우는 고려하지 않는다.
이문제가 조금은 쉽게 느껴지는경 바로 숫자 3개로 제한 했기 때문일것이다.
만일 제한이 없었다면 어땠을까?
고려 해야 할 사항들이 늘어난다.
갯수 상관없이 소수인 경우를 모두 고려해야하고,
중복되는 결과에 대해서는 카운트 처리를 하지 않아야 한다.
3. 구현
3.1 핵심 코드
소수인지 판별하는 코드는 따로 첨부하지 않고 넘어가도록 하겠다. 물론 맨아래 전체 코드에는 넣어두었다.
solution 함수 내부에서 배열의 크기만큼 DFS를 돌려준다.
순차적으로 방문하는데, 한번 방문한 숫자는 방문할 필요가 없다. (어차피 모두 더해야 하므로)
int solution(vector<int> nums) {
for(int i=0;i<nums.size();i++){
dfs();
}
...
}
DFS 함수의 파라미터를 살펴보자.
중요한 파라미터는 2,3,4 번째 파리미터이다.
2번째 파라미터는 이제까지 더한 값이고, 3번째 파라미터는 현재 배열의 몇번째 위치인가를 나타내는 인덱스이다.
가장 중요한 4번째 파라미터는 현재까지 몇개의 숫자를 더했는지 확인하는 변수이다.
int dfs(vector<int> nums, int sum, int index, int cnt);
이제부터는 DFS 함수의 구현이다.
우선 가장먼저 현재까지 더한 숫자의 갯수가 3개 이상이면 더이상 탐색을 진행 할 필요가 없으니 가장 먼저 처리해준다.
몇개인지 모르고 다 더해서 소수가 되었는지 알고보니 5개를 더했다면, 카운트 할 필요가 없기 때문이다.
if(cnt>3){
return 0;
}
그다음은 3개인 경우에는 어떻게 할것인가 하는 문제이다.
3개인 경우 소수인지 확인 하고 소수이면 경우의 수를 1증가시키고 탐색을 종료한다.
result 변수는 전역 변수로 소수인 경우의 수를 카운트 한다.
if(cnt==3){
if(is_prime(sum)==1){
result+=1;
}
return 0;
}
파리미터로 현재의 위치를 넘겨주는 이유는 다음의 코드에서 확인 할 수 있다.
배열을 왼쪽에서 오른쪽으로 탐색하는데, 이경우 이전에 탐색한 곳은 탐색할 필요가 없다.
그래서 다음 인덱스(현재 인덱스도 결국 방문한곳)부터 숫자의 합과 다음 인덱스에 해당되는 값을 더하며 탐색을 한다.
for(int i=index+1; i<nums.size(); i++){
dfs(nums, sum+nums[i], i, cnt+1);
}
결과적으로 DFS를 통해 순차적으로 탐색 한다.
탐색하면서 더한 숫자의 갯수가 3개인 경우에 소수인지 확인 한 뒤, 소수면 결과값에 1를 더해준다.
3.2 전체 코드
#include <vector>
#include <iostream>
using namespace std;
int result = 0;
int dfs(vector<int> nums, int sum, int index, int cnt);
int is_prime(int number);
void clear_visit(void);
int solution(vector<int> nums) {
for(int i=0;i<nums.size();i++){
dfs(nums, nums[i], i, 1);
}
return result;
}
int dfs(vector<int> nums, int sum, int index, int cnt){
if(cnt>3){
return 0;
}
if(cnt==3){
if(is_prime(sum)==1){
result+=1;
}
return 0;
}
for(int i=index+1; i<nums.size(); i++){
dfs(nums, sum+nums[i], i, cnt+1);
}
return 0;
}
int is_prime(int number){
if(number < 2){
return -1;
}
for(int i=2;i<number;i++){
if(number%i==0){
return -1;
}
}
return 1;
}