문제 개요
일렬로 서 있는 n명의 병사가 있다고 가정해 봅시다. 각 병사에게는 서로 다른 고유한 평점(rating) 값이 부여되어 있습니다. 우리는 다음 규칙에 따라 이들 중 3명으로 구성된 팀을 만들어야 합니다.
인덱스 (i, j, k)를 가진 3명의 병사를 선택하며, 이때 i < j < k를 만족해야 합니다. 팀이 유효하기 위한 조건은 다음 두 가지 중 하나입니다.
- rating[i] < rating[j] < rating[k] — 평점이 오름차순
- rating[i] > rating[j] > rating[k] — 평점이 내림차순
즉, 만들 수 있는 유효한 팀의 총 개수를 구하는 것이 목표입니다. 한 병사는 여러 팀에 동시에 속할 수 있습니다.
예시
예를 들어 입력이 rating = [2, 5, 3, 4, 1]이라면 출력은 3이 됩니다. 다음 세 팀을 만들 수 있기 때문입니다.
- (2, 3, 4) — 오름차순
- (5, 4, 1) — 내림차순
- (5, 3, 1) — 내림차순
풀이 접근 방법
이 문제는 완전 탐색(brute force)으로 해결할 수 있습니다. 가능한 모든 인덱스 조합 (i, j, k)를 확인하면서 오름차순 또는 내림차순 조건을 만족하는 경우의 수를 세면 됩니다.
- 결괏값을 저장할 변수 ret을 0으로 초기화하고, 배열의 크기를 n에 저장합니다.
- 세 개의 중첩 반복문을 사용해 i < j < k를 만족하는 모든 조합을 탐색합니다.
- v[i] < v[j] < v[k] 또는 v[i] > v[j] > v[k]를 만족하면 ret을 1씩 증가시킵니다.
- 모든 탐색이 끝나면 ret을 반환합니다.
C++ 구현 코드
아래 예제를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numTeams(vector<int>& v) {
int ret = 0;
int n = v.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (v[i] < v[j] && v[j] < v[k])
ret++;
else if (v[i] > v[j] && v[j] > v[k])
ret++;
}
}
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {2,5,3,4,1};
cout << (ob.numTeams(v));
}
입력
{2,5,3,4,1}출력
3
복잡도 분석
이 알고리즘은 세 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n³)입니다. 추가적인 배열을 사용하지 않으므로 공간 복잡도는 O(1)입니다. n이 작은 경우에는 충분히 효율적이지만, n이 커질 경우 각 원소를 중간 지점으로 삼아 좌측과 우측의 증가·감소 개수를 세는 O(n²) 최적화 기법을 활용하면 성능을 더욱 개선할 수 있습니다.