柠檬水找零 문제

입력과 응답 시나리오가 고정된 문제의 경우, 단순하게 구현하면 된다.

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
         unordered_map cash;
         for(int i = 0;i < bills.size();i++){
            int change = bills[i] - 5;
            if(change == 0){
               cash[bills[i]]++;
               continue;
            }else if(change == 5){
               if(cash[5] != 0){
                  cash[bills[i]]++;
                  cash[5]--;
                  
                  continue;
               }else{
                  return false;
               }
            }else if(change == 15){
               if(cash[5] != 0 && cash[10] != 0){
                  cash[bills[i]]++;
                  cash[5]--;
                  cash[10]--;
                  continue;
               }else if(cash[5] >= 3 && cash[10] == 0){
                  cash[bills[i]]++;
                  cash[5]--;
                  cash[5]--;
                  cash[5]--;
                  continue;
               }else{
                  return false;
               }
            }
         }
         return true;
    }
};

根据身高重建队列 문제

두 개의 차원을 고려해야 하는 요소 문제가 있다. 이러한 경우 두 차원이 완전히 독립적이지 않을 수 있으므로 주의해야 한다. 한 차원을 먼저 결정한 다음, 그基础上에서 다른 차원을 확정하면 된다. 어떤 차원을 먼저 처리할지는 실제로 테스트를 통해 확인하는 것이 좋다. 일반적으로 두 차원에 상관관계가 있다면, 정렬할 때 다른 차원의 의미와 맞추는 것이 중요하다.

단일 차원 정렬의 경우에도 이전 단계의 결과를 유지하면서 처리해야 한다.

class Solution {
public:
    static bool comp(const vector<int> & a,const vector<int> & b){
           if(a[0] > b[0]){
              return true;
            }else if(a[0] == b[0]){
              if(a[1] < b[1]){
                return true;
              }
            }
           return false;
    } 
    vector reconstructQueue(vector& people) {
         vector result;
         sort(people.begin(),people.end(),comp);
         for(int i = 0;i < people.size();i++){
              result.insert(result.begin() + people[i][1], people[i]);
         }
         return result;
    }
};

用最少数量的箭引爆气球 문제

중복 구간 문제가 특히 중요합니다. 중복 구간 내부를 처리해야 하는 문제, 예를 들어 중복 구간을 통계내거나 삭제하는 문제가 있습니다.

해결 방법:

1. 먼저 정렬한다. 구간의 시작점을 기준으로 정렬하고, 정렬된 순서대로 각 구간을 처리한다.
2. 현재 구간의 왼쪽 경계가 이전 구간의 오른쪽 경계보다 작거나 같으면, 중복 구간이 형성된다. 실제로 이전에 형성된 중복 구간과 새로운 구간을 비교하여 중복 구간에 포함시킬 수 있는지 확인한다. (여러 구간이 형성한 중복 구간의 오른쪽 경계는 매번 새로 추가된 구간의 오른쪽 경계와 최소값을 취해야 한다.)
3. 현재 구간의 왼쪽 경계가 이전 구간의 오른쪽 경계보다 크면, 중복 구간이 아니므로 새로운 구간을 시작한다.

class Solution {
public:
    static bool comp(const vector<int> & a,const vector<int> & b){
          return a[0] < b[0];
    }
    int findMinArrowShots(vector& points) {
       int count = 1;
       sort(points.begin(),points.end(),comp);
       for(int i = 1;i < points.size();i++){
          if(points[i-1][1] < points[i][0]){
             count++;
          }else{
            points[i][1] = min(points[i-1][1], points[i][1]);
          }
       }
       return count;
    }
};