1711 Count Good Meals

입력으로 주어진 음식들 중에서 두 개를 선택했을 때, 맛있는 정도의 합이 2의 지수가 되는 경우의 수를 찾는 문제이다.

문제를 봤을 때, 바로 조합을 이용하는 방법이 생각났지만, 시간 복잡도 상 당연히 조합은 안 되었다.

그래서 일단 맛있는 정도를 Key, 등장 횟수를 value로 하는 해쉬맵을 만들고, 해당 해쉬맵을 순회하면서

모든 경우의 수를 찾는 시간복잡도 O(N)의 방법으로 해결했다.

 

여담으로 리트코드 채점 서버가 좀 이상한 거 같다.

같은 코드를 제출해도 수행시간이 2배까지도 차이가 났다...

음... 백준처럼 채점 서버에 제출이 몰리면 순차적으로 수행하는 게 아니라 그냥 동시에 돌리는 건가

 

 

C++

class Solution {
public:
    int countPairs(vector<int>& deliciousness) {
        vector<int> two;
        for(int i = 0;i < 22; ++i)
            two.push_back(pow(2,i));
        
        unordered_map<int, long long> meals;
        
        for(size_t i=0;i<deliciousness.size();++i)
            if (meals.find(deliciousness[i])!=meals.end())
                ++meals[deliciousness[i]];
            else
                meals[deliciousness[i]] = 1;
        
        int cnt{};
        long long temp;
        
        for(auto it = meals.begin(); it!=meals.end(); ++it){
            int t = 0;
            while(t < 22 && it -> first * 2 >= two[t]) ++t;
            if (t != 0 && it -> first * 2 == two[t - 1]){
                temp = it -> second;
                cnt = (cnt + temp * (temp - 1) / 2 % 1000000007) % 1000000007;
            }
            for(;t < 22; ++t){
                temp = two[t] - it -> first;
                if (meals.find(temp)!=meals.end()){
                    cnt = (cnt + it -> second * meals[temp] % 1000000007) % 1000000007;
                }
            }
        }
        return cnt;
    }
};

Python

class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        two = [1<<i for i in range(22)]
        meals = dict()
        
        for d in deliciousness:
            if d in meals:
                meals[d] += 1
            else:
                meals[d] = 1
        
        cnt = 0
        
        for meal in meals.keys():
            t = 0
            while t < 22 and meal * 2 >= two[t]:
                t += 1
            if (t != 0 and meal * 2 == two[t - 1]):
                temp = meals[meal]
                cnt = (cnt + temp * (temp - 1) / 2 % 1000000007) % 1000000007
            
            while t < 22:
                temp = two[t] - meal
                if temp in meals.keys():
                    cnt = (cnt + meals[meal] * meals[temp] % 1000000007) % 1000000007
                t += 1
            
        return int(cnt)