Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 알고리즘 풀이: 다른 목록의 부분 집합이 아닌 선호 회사 목록을 가진 사람 찾기

문제 개요

favoriteCompanies라는 배열이 주어집니다. 여기서 favoriteCompanies[i]는 i번째 사람이 선호하는 회사 목록을 의미합니다. 우리가 찾아야 할 것은 자신의 선호 회사 목록이 다른 어떤 사람의 목록에도 부분 집합으로 포함되지 않는 사람들의 인덱스입니다.

예시로 이해하기

입력이 다음과 같다고 가정해 보겠습니다.

favoriteCompanies = [["TCS", "google", "facebook"], ["google", "microsoft"], ["google", "facebook"], ["google"], ["amazon"]]

이때 출력은 [0, 1, 4]가 됩니다. 그 이유는 다음과 같습니다.

  • 인덱스 2인 사람의 목록 ["google", "facebook"]은 인덱스 0인 사람의 목록 ["TCS", "google", "facebook"]의 부분 집합입니다.
  • 인덱스 3인 사람의 목록 ["google"]은 인덱스 0인 사람의 목록과 인덱스 1인 사람의 목록 ["google", "microsoft"] 양쪽 모두의 부분 집합입니다.
  • 나머지 목록들은 어느 목록의 부분 집합도 아니므로 최종 정답은 [0, 1, 4]입니다.

해결 접근 방법

이 문제는 크게 두 단계로 나누어 접근할 수 있습니다. 첫째, 한 배열이 다른 배열의 부분 집합인지 판별하는 함수를 만듭니다. 둘째, 이 함수를 활용해 각 사람의 목록을 나머지 모든 목록과 비교합니다.

1단계: 부분 집합 검사 함수 ok() 정의

ok() 함수는 두 개의 문자열 배열 a와 b를 매개변수로 받습니다. 두 배열은 미리 정렬되어 있어야 하며, 두 포인터(two-pointer) 기법으로 a의 모든 원소가 b에 포함되어 있는지 확인합니다.

  1. 카운터와 포인터를 초기화합니다: cnt := 0, i := 0, j := 0
  2. i가 a의 크기보다 작고 j가 b의 크기보다 작은 동안 다음을 반복합니다.
    • a[i]와 b[j]가 같으면 → i, j, cnt를 각각 1씩 증가
    • a[i]가 b[j]보다 작으면 → i만 1 증가
    • 그 외의 경우 → j만 1 증가
  3. 반복이 끝난 후 cnt가 a의 크기보다 작으면 true를 반환합니다. 이는 a가 b의 부분 집합이 아니라는 의미입니다.

2단계: 메인 메서드에서 전체 목록 비교

  1. 정수를 담을 집합(set) s를 하나 정의합니다.
  2. n := f의 크기로 설정합니다.
  3. 첫 번째 반복문에서 각 목록 f[i]를 사전순으로 정렬합니다.
  4. 두 번째 반복문에서 각 인덱스 i에 대해 다음을 수행합니다.
    • 플래그 c := true로 초기화합니다.
    • j가 0부터 n-1까지 순회하며, i와 j가 같으면 해당 반복은 건너뛰고, 그렇지 않으면 c := c AND ok(f[i], f[j])를 수행합니다.
    • 모든 비교 후 c가 참이면 i를 집합 s에 삽입합니다.
  5. 모든 비교가 끝나면 s의 원소들을 배열 형태로 반환합니다.

C++ 구현 예제

아래 구현을 통해 동작 과정을 더 명확하게 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    bool ok(vector<string>& a, vector<string>& b){
        int cnt = 0;
        int i = 0;
        int j = 0;
        while (i < a.size() && j < b.size()) {
            if (a[i] == b[j]) {
                i++;
                j++;
                cnt++;
            }
            else if (a[i] < b[j]) {
                i++;
            }
            else {
                j++;
            }
        }
        return cnt < a.size();
    }
    vector<int> peopleIndexes(vector<vector<string> >& f){
        set<int> s;
        int n = f.size();
        for (int i = 0; i < n; i++) {
            sort(f[i].begin(), f[i].end());
        }  
        for (int i = 0; i < n; i++) {
            bool c = true;
            for (int j = 0; j < n; j++) {
                if (i == j)
                    continue;
                c &= ok(f[i], f[j]);
            }
            if (c)
                s.insert(i);
        }
        return vector<int>(s.begin(), s.end());
    }
};
main(){
    Solution ob;
    vector<vector<string>> v = {{"TCS","google","facebook"},{"google","microsoft"},{"google","facebook"},{"google"},{"amazon"}};
    print_vector(ob.peopleIndexes(v));
}

입력

{{"TCS","google","facebook"},{"google","microsoft"},{"google","facebook"},{"google"},{"amazon"}}

출력

[0, 1, 4]

시간 복잡도 분석

각 목록을 정렬하는 데 O(m log m)이 소요되며, 서로 다른 두 목록의 모든 쌍을 비교하는 데 O(n² × m)이 필요합니다. 따라서 전체 시간 복잡도는 대략 O(n² × m + n × m log m)입니다. 여기서 n은 사람 수, m은 목록의 평균 길이를 의미합니다. 두 포인터 기법 덕분에 각 비교가 선형 시간 안에 처리되어 효율적인 풀이가 가능합니다.