[LeetCode] 1395. Count Number of Teams

https://leetcode.com/problems/count-number-of-teams/description/?envType=daily-question&envId=2024-07-29

leetcode - Count Number of Teams

문제 유형 : 투 포인터

문제 난이도 : Medium

 

 

문제

There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

• Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).
• A team is valid if: (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

 

n명의 군인들이 일렬로 서 있다.

각 군인은 고유한 rating 값을 가지고 있다.

한 팀당 3명씩 맞춰서 팀을 구성해야 한다.

raiting의 규칙으로는, 한 방향으로 점점 커지는 순이거나 한 방향으로 점점 작아지는 순이여야 한다.

조건에 맞도록 팀을 구성시키는 경우의 수를 구하시오. 중복 소속이 가능합니다.

 

풀이

j를 1부터 n-1 전까지 순회하면서, 0 ~ j-1, j+1 ~ n-1까지의 범위에서 각각 더 큰 수의 값, 더 작은 수의 값을 양방향에서 센다.

그 뒤, 매 번의 j마다 (왼쪽 범위에서 rating[j]보다 작은수의 개수) * (오른쪽 범위에서 rating[j]보다 큰 수의 개수) + (왼쪽 범위에서 rating[j]보다 큰수의 개수) * (오른쪽 범위에서 rating[j]보다 작은 수의 개수)를 구해서 누적시킨다.

 

순회가 끝나면, 반환한다.

 

 

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int numTeams(vector<int>& rating) {
        int n = rating.size();
        if (n < 3) return 0; // Not enough elements to form a team
        
        int teams = 0;
        for (int j = 1; j < n-1; j++) {
            int leftSmaller = 0, leftGreater = 0;
            int rightSmaller = 0, rightGreater = 0;
            
            for (int i = 0; i < j; i++) {
                if (rating[i] < rating[j]) leftSmaller++;
                if (rating[i] > rating[j]) leftGreater++;
            }
            
            for (int k = j+1; k < n; k++) {
                if (rating[k] < rating[j]) rightSmaller++;
                if (rating[k] > rating[j]) rightGreater++;
            }
            
            teams += leftSmaller * rightGreater + leftGreater * rightSmaller;
        }
        
        return teams;
    }
};