삼총사(Lv.1)
✅ 문제 설명
한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다. 예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다.
한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요.
✅ 제한사항
3 ≤ number의 길이 ≤ 13
-1,000 ≤ number의 각 원소 ≤ 1,000
서로 다른 학생의 정수 번호가 같을 수 있습니다.
🔽 소스코드 1 (반복문 사용)
💻 풀이
-
3개의 수의 조합을 찾기 위해서 3개의 for문을 사용하는 방법이다.
-
반복문이 많아질 경우 시간 복잡도는 최대
O(n³)가 되지만, 문제 조건 속 배열의 최대 길이가 13이므로 충분히 빠르게 구현할 수 있다. -
먼저 0부터 시작하는 i를 기준으로
i < j < k조건을 두어 반복문을 실행하고, -
마지막에는 3개의 합이 0일 경우
count++를 통해 하나의 조합이 있음을 설정해준다.
⌛ 시간 0.02ms ~ 0.03ms
public int solution(int[] number) {
int count = 0;
for(int i = 0; i < number.length; i++) {
for(int j = i + 1; j < number.length; j++) {
for(int k = j + 1; k < number.length; k++) {
if(number[i] + number[j] + number[k] == 0) {
count++;
}
}
}
}
return count;
}🔽 소스코드 2 (재귀함수 사용)
💻 풀이
-
배열의 길이가 길거나, 혹은 조합할 원소의 개수가 유동적인 경우,
→ 반복문보다 재귀 함수를 사용하는 것이 유리하다. -
메인 함수에서는 재귀 조합을 위한
combine()함수를 호출하여
→ 조합을 시작하게 된다. -
재귀 함수
combine()내부에서는 다음과 같은 조건으로 동작한다: -
현재까지 선택한 원소의 개수(
depth)가 목표 개수(예: 3)에 도달하면,
→ 누적된 합을 기준으로 조건을 판단하고count++등의 처리를 한다.
→ 이후 더 이상 탐색하지 않고return하여 현재 호출을 종료한다. -
depth가 목표보다 작을 경우, 반복문을 통해 남은 원소들을 순회하며
→combine()을 자기 자신을 다시 호출한다 (다음 원소 선택). -
이와 같은 재귀 호출은 반복문 내에서 이루어지며,
→ 반복문이 더 이상 실행되지 않는 조건 (즉,i >= 배열 길이)이 되면 해당 호출은 종료된다. -
결과적으로, 모든 재귀 호출이 종료되고, 가능한 모든 조합을 탐색했을 때
→ 메인 함수의combine()호출도 완전히 종료된다.
⌛ 시간 0.02ms ~ 0.08ms
int count = 0;
public int solution1(int[] number) {
combine(number, 0,0,0);
return count;
}
private void combine(int[] number, int start, int depth, int sum) {
if(depth == 3) {
if(sum == 0) count++;
return;
}
for(int i = start; i < number.length; i++) {
combine(number, i + 1, depth + 1, sum + number[i]);
}
}