[레벨 1] 프로그래머스 오늘의 문제 : 삼총사 - next_permutation으로 조합 구현하기
오늘의 코테 연습문제는 프로그래머스의
삼총사 문제다.
문제 링크는 아래와 같다.
https://school.programmers.co.kr/learn/courses/30/lessons/131705?language=cpp
문제 설명
한국중학교 학생들은 각자 정수 번호를 하나씩 가지고 있다.
이 중 3명의 정수 번호를 더했을 때 합이 0이 되면
이 세 학생을 삼총사라고 한다.
예를 들어 다음과 같은 학생들이 있다고 해보자.
[-2, 3, 0, 2, -5]여기서
-2 + 0 + 2 = 0
3 + 2 + (-5) = 0이므로 만들 수 있는 삼총사는 총 2개다.
결국 문제에서 요구하는 것은 간단하다.
학생들 중 3명을 선택했을 때
세 학생의 번호 합이 0이 되는 경우의 수를 구하면 된다.
제한 사항
3 ≤ number의 길이 ≤ 13
-1,000 ≤ number의 각 원소 ≤ 1,000
서로 다른 학생의 정수 번호가 같을 수 있다.여기서 마지막 조건이 꽤 중요하다.
번호가 같다고 해서 같은 학생은 아니다.
예를 들어
[-1, -1, 0, 1, 1]에서 첫 번째 -1과 두 번째 -1은
같은 값을 가지고 있지만 서로 다른 학생이다.
즉 이 문제에서는 단순히 숫자만 보는 것이 아니라
각 위치에 존재하는 서로 다른 학생을 선택한다고 생각해야 한다.
처음 문제를 봤을 때
문제를 읽자마자 든 생각은 이거였다.
음... 완전탐색 문제인가?
학생 수가 최대 13명밖에 되지 않고
그중 3명을 선택하면 된다.
그러면 경우의 수는 그냥
number.size() C 3이다.
즉,
모든 3명의 조합을 확인한다.
↓
세 학생의 번호를 더한다.
↓
합이 0이면 answer++하면 된다.
아이디어 자체는 상당히 간단해 보였다.
그래서 처음에는 별생각 없이
next_permutation()을 이용하면 되겠다고 생각했다.
먼저 도메인 지식부터 정리해보자
이 문제에서 가장 중요한 것은
완전탐색, 그리고 순열과 조합의 차이다.
완전탐색이란?
완전탐색(Brute Force)은 말 그대로
가능한 모든 경우를 직접 확인하는 방법이다.
이번 문제에서는
학생 3명을 선택할 수 있는 모든 경우를 확인하면 된다.
학생이 N명이라면
3명을 선택하는 경우의 수는
N C 3이다.
문제에서 학생 수는 최대 13명이므로
13C3 = 286밖에 되지 않는다.
따라서 모든 경우를 직접 확인해도 충분히 빠르다.
즉 이 문제는
"완전탐색을 사용해도 되는가?"
를 고민할 필요는 거의 없었다.
진짜 중요한 문제는
모든 경우를 어떤 방식으로 만들 것인가?
였다.
순열과 조합의 차이
순열(Permutation)
순열은 순서를 고려해서 선택하는 것이다.
예를 들어 A, B, C라는 세 사람이 있다면
A B C
A C B
B A C
B C A
C A B
C B A를 모두 서로 다른 경우로 본다.
반면 조합은 순서를 고려하지 않는다.
A, B, C라는 세 사람을 선택했다면
A, C, B
B, A, C
C, B, A는 전부 같은 세 사람을 선택한 것이다.
이번 문제에서 필요한 것은
순열 X
조합 O이다.
첫 번째 문제풀이
하지만 처음에는 이 부분을 깊게 생각하지 않고
다음과 같은 코드를 작성했다.
#include <bits/stdc++.h>
using namespace std;
int solution(vector<int> number) {
int answer = 0;
do {
int sum = 0;
for (int i = 0; i < 3; i++) {
sum += number[i];
}
if (sum == 0) {
answer++;
}
} while (next_permutation(number.begin(), number.end()));
return answer;
}처음 봤을 때는 나름 그럴싸했다.
next_permutation()으로 모든 경우를 만든다.
↓
앞의 3개 숫자를 더한다.
↓
0이면 삼총사다.그런데 생각해보니 이건 아니었다.
문제는 숫자가 아니라 "사람"을 선택하는 것이다
예를 들어 다음 배열이 있다고 해보자.
[-2, 3, 0, 2, -5]이를 학생의 관점에서 보면 다음과 같다.
0번 학생 → -2
1번 학생 → 3
2번 학생 → 0
3번 학생 → 2
4번 학생 → -5즉 우리가 선택해야 하는 것은
숫자 자체가 아니라 학생의 인덱스다.
예를 들어
0번 학생
2번 학생
3번 학생을 선택했다면
-2 + 0 + 2 = 0이므로 하나의 삼총사가 된다.
그런데 이 세 사람의 순서를 바꾼다고 해서
새로운 삼총사가 되는 것은 아니다.
next_permutation(number)이 문제가 되는 이유
next_permutation(number)으로 배열 자체의 모든 순열을 만들면
같은 세 사람이 앞의 세 자리에 등장하는 경우가 여러 번 생긴다.
예를 들어 선택된 사람이 A, B, C라면
A B C
A C B
B A C
B C A
C A B
C B A는 전부 같은 세 사람이다.
하지만 배열의 순열을 기준으로 보면
서로 다른 경우로 취급된다.
즉 내가 처음 작성한 코드는
조합을 세어야 하는데
순열을 만들고 있었던 것이다.
우리가 원하는 것은
nP3가 아니라
nC3이다.
문제는 완전탐색이 맞았다.
하지만 완전탐색해야 하는 대상이 순열이 아니라 조합이었다.
그런데 조합을 어떻게 구현하지?
여기까지는 알았다.
이 문제는 순열이 아니다.
조합이다.그런데 막상 구현하려고 하니 고민이 생겼다.
next_permutation()을 이용해서 조합을 만들 수는 없을까?
아무리 생각해도 아이디어가 바로 떠오르지 않았다.
이 시점에서 AI에게 문제를 풀어달라고 한 것이 아니라
현재 상황에서 사용할 수 있는 아이디어가 무엇인지 물어봤다.
그러자 생각하지 못했던 방법을 알게 됐다.
0과 1로 선택 여부를 표현한다
예를 들어 학생이 5명이고
그중 3명을 선택해야 한다고 해보자.
다음과 같은 배열을 만든다.
vector<int> select = {0, 0, 1, 1, 1};여기서
0 = 선택하지 않음
1 = 선택함이라고 생각하는 것이다.
예를 들어
0 0 1 1 1이라면 2번, 3번, 4번 학생을 선택한 하나의 조합이다.
여기에 next_permutation을 사용하면?
이제 select 배열에 next_permutation()을 사용한다.
do {
} while (next_permutation(select.begin(), select.end()));그러면 다음과 같은 패턴들이 만들어진다.
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 0
1 0 0 1 1
...모든 배열에는 항상 1이 정확히 3개 존재한다.
즉 학생 N명 중 정확히 3명을 선택한 모든 경우가 만들어진다.
이걸 보고 조금 허무했다.
아...
next_permutation()으로 학생들의 번호를 섞는 것이 아니라
선택 여부를 섞으면 되는구나.
왜 이 방법은 중복되지 않을까?
예를 들어
0 1 1 0 1은 1번, 2번, 4번 학생을 선택했다는 뜻이다.
여기에서 1 세 개는 서로 구분되지 않는다.
중요한 것은 오직
어느 위치가 1인가?이다.
따라서 서로 다른 select 배열 하나가
서로 다른 학생 조합 하나와 정확하게 대응한다.
학생이 5명이라면 만들어지는 경우의 수도 정확하게
5C3 = 10개가 된다.
next_permutation은 정렬 후 사용해야 한다
next_permutation()은 현재 순열보다
사전순으로 바로 다음에 오는 순열을 만들어준다.
따라서 모든 순열을 탐색하려면
가장 작은 순열부터 시작하는 것이 안전하다.
처음 select는
1 1 1 0 0이므로 정렬한다.
sort(select.begin(), select.end());그러면
0 0 1 1 1이 된다.
이 상태에서 next_permutation()을 반복하면
모든 선택 조합을 빠짐없이 확인할 수 있다.
두 번째 문제풀이
바로 이 아이디어를 적용했다.
#include <bits/stdc++.h>
using namespace std;
int solution(vector<int> number) {
int answer = 0;
vector<int> select(number.size());
for (int i = 0; i < 3; i++) {
select[i] = 1;
}
sort(select.begin(), select.end());
do {
int sum = 0;
for (int i = 0; i < number.size(); i++) {
if (select[i] == 1) {
sum += number[i];
}
}
if (sum == 0) {
answer++;
}
} while (next_permutation(select.begin(), select.end()));
return answer;
}결과는?
정답이었다!
그런데 사실 더 간단한 방법도 있다
문제를 풀고 나서 생각해보니
이 문제에서는 반드시 next_permutation()을 사용할 필요는 없다.
선택해야 하는 사람이 정확히 3명으로 고정되어 있기 때문에
3중 for문으로도 상당히 간단하게 풀 수 있다.
#include <bits/stdc++.h>
using namespace std;
int solution(vector<int> number) {
int answer = 0;
for (int i = 0; i < number.size(); i++) {
for (int j = i + 1; j < number.size(); j++) {
for (int k = j + 1; k < number.size(); k++) {
if (number[i] + number[j] + number[k] == 0) {
answer++;
}
}
}
}
return answer;
}항상
i < j < k가 유지되기 때문에 같은 세 학생을 순서만 바꿔 중복해서 세지 않는다.
개인적으로 실제 코딩테스트에서 이 문제를 다시 만난다면
3중 for문을 사용할 것 같다.
하지만 이번 문제를 통해
next_permutation()을 조합 생성에도 활용할 수 있다는 것을 배운 점은 꽤 의미 있었다.
시간복잡도
학생 수를 N이라고 하면 확인해야 하는 조합의 수는
N C 3이다.
문제에서는
N ≤ 13이므로 최대 조합 수도
13C3 = 286밖에 되지 않는다.
따라서 이 문제에서는 복잡한 최적화보다
정확하게 조합을 구현할 수 있는가가 더 중요하다.
문제를 풀고 나서
개인적으로 이 문제는 아이디어 자체는 상당히 쉬운 문제라고 생각한다.
문제를 읽으면 거의 바로
3명을 뽑는다.
↓
합이 0인지 확인한다.가 떠오른다.
즉 완전탐색이라는 것까지는 어렵지 않았다.
하지만 막상 구현하려고 하니
"모든 경우"와 "모든 순서"는 다르다.
라는 것을 다시 생각하게 됐다.
처음에는 next_permutation()이라는 함수를 알고 있으니
그냥 모든 순열을 만들면 되겠다고 생각했다.
하지만 문제에서 요구하는 것은 순열이 아니라 조합이었다.
그리고 이번 문제에서 가장 기억에 남았던 것은
next_permutation()으로 조합도 만들 수 있다는 점이었다.
0 = 선택하지 않음
1 = 선택함으로 표현하고
0 0 1 1 1을 next_permutation()으로 순회하면
선택 위치의 모든 조합을 만들 수 있다.
함수 하나를 알고 있는 것과
그 함수를 어떻게 활용할 수 있는지를 아는 것은
확실히 다른 문제인 것 같다.
결론
이번 문제에서 가져갈 것은 크게 세 가지다.
1. 완전탐색 문제에서도 순열과 조합을 먼저 구분해야 한다.
2. next_permutation()은 숫자 자체뿐 아니라
0/1 선택 배열을 이용해 조합 생성에도 활용할 수 있다.
3. 뽑는 개수가 고정되어 있다면
중첩 for문이 오히려 더 단순하고 직관적일 수 있다.결국 이 문제는 단순히
세 수의 합이 0인가?를 묻는 문제가 아니었다.
순열과 조합의 차이를 이해하고,
원하는 경우의 수를 코드로 정확하게 만들어낼 수 있는가?
를 묻는 문제에 더 가까웠다고 생각한다.
앞으로 완전탐색 문제가 나오면
무작정 next_permutation()부터 떠올리기보다
순서가 중요한가?
↓
순열
순서가 중요하지 않은가?
↓
조합을 먼저 판단해야겠다.
