LeetCode 475. Heaters (C++)

The link : https://leetcode.com/problems/heaters/

Heaters - LeetCode

문제 요약

 

집들의 위치가 적힌 houses배열과 히터들의 위치가 적인 heaters 배열이 있습니다.

모든 집들을 따듯하게 만들기 위한 heater의 최소 반지름을 구하세요.

하나의 반지름은 모든 heaters에게 적용됩니다.

 

핵심 포인트

 

집과 배열의 최대 길이는 3만이므로, 무턱대고 for문을 남발하다가는 시간초과가 발생합니다.

때문에 다음 공식을 적절히 활용하여, for문을 한 번씩만 돌려도 답을 구할 수 있게끔 구현합니다.

 

 

1. 각 집을 기준으로 가장 가까운 왼쪽에 위치한 히터의 거리
2. 각 집을 기준으로 가장 가까운 오른쪽에 위치한 히터의 거리

= 히터의 거리는 최소값만 갱신하며,
정답을 출력할때는 가장 히터의 길이가 큰 값을 출력한다.

 

 

문제 풀이

 

1. 필요한 변수들을 선언하고 houses벡터와 heaters 벡터를 오름차순으로 정렬합니다.

        int ans = 0;
        vector<int> dis(houses.size(),INT_MAX); // 히터의 최소 반지름을 저장할 벡터
        sort(houses.begin(),houses.end());
        sort(heaters.begin(),heaters.end());

 

2. 먼저 각 집을 기준으로 가장 가까운 오른쪽에 위치한 히터의 거리를 저장합니다.

        // Right
        for(int i=0,j=0; i<houses.size(); i++){ // 1
            if(j>=heaters.size()) break;  // 2
            if(houses[i]<=heaters[j]){ // 3
                dis[i]=heaters[j]-houses[i]; // 4
            }   
            else i--,j++; // 5
        }

(1) i는 집의 위치, j는 히터의 위치입니다. '집'을 중심으로 가장 가까운 왼쪽에 위치한 히터의 거리를 구해야 하므로, for문은 houses의 사이즈만큼 돌립니다.

(2) 만약 j가 heaters.size() 이상일 경우, 가능 범위를 초과했다는 뜻이므로 for문을 빠져나갑니다.

(3) houses[i] <= heaters[i]일 경우, 해당 히터가 현재 집에서 가장 가까운 왼쪽에 위치한 히터이므로 dis에 그 거리를 갱신해줍니다.

(4) 그렇지 않을 경우 i--(다음 for문에서도 현재 집 위치를 유지), j++(다음 히터로 위치를 옮김)을 해줍니다.

 

3. 다음으로 각 집을 기준으로 가장 가까운 왼쪽에 위치한 히터의 거리를 저장합니다.

        // Left
        for(int i=houses.size()-1, j=heaters.size()-1; i>=0; i--){ // 1
            if(j<0) break; // 2
            if(houses[i]>=heaters[j]){ // 3
                dis[i] = min(dis[i],houses[i]-heaters[j]); // 4
            }
            else i++,j--; // 5
        }

(1) i는 집의 위치, j는 히터의 위치입니다. '집'을 중심으로 가장 가까운 오른에 위치한 히터의 거리를 구해야 하므로, for문은 houses의 사이즈만큼 돌립니다.

(2) 만약 j가 0보다 작을 경우, 가능 범위를 초과했다는 뜻이므로 for문을 빠져나갑니다.

(3)  houses[i] >= heaters[i]일 경우, 해당 히터가 현재 집에서 가장 가까운 오른에 위치한 히터이므로 dis에 그 거리를 갱신해줍니다.

(4) 그렇지 않을 경우 i++(다음 for문에서도 현재 집 위치를 유지), j--(다음 히터로 위치를 옮김)을 해줍니다.

 

4. 모든 집을 따듯하게 만들 수 있는 가장 짧은 반지름을 찾고 정답으로 반환합니다.

        for(int i=0; i<dis.size(); i++) if(dis[i]>ans) ans = dis[i];
        return ans;

 

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        int ans = 0;
        vector<int> dis(houses.size(),INT_MAX);
        sort(houses.begin(),houses.end());
        sort(heaters.begin(),heaters.end());
        for(int i=0,j=0; i<houses.size(); i++){ // Right
            if(j>=heaters.size()) break;
            if(houses[i]<=heaters[j]){
                dis[i]=heaters[j]-houses[i];
            }   
            else i--,j++;
        }
        for(int i=houses.size()-1, j=heaters.size()-1; i>=0; i--){ // Left
            if(j<0) break;
            if(houses[i]>=heaters[j]){
                dis[i] = min(dis[i],houses[i]-heaters[j]);
            }
            else i++,j--;
        }
        for(int i=0; i<dis.size(); i++) if(dis[i]>ans) ans = dis[i];
        return ans;
    }
};