[BOJ] 풍선 맞추기 - 11509

📃 문제

[BOJ] 풍선 맞추기 🔗링크

처음에는 문제를 잘 못 이해해서, 화살이 오른쪽으로 이동할때마다 높이가 1씩 줄어드는 줄 알았다.
화살이 풍선을 맞출때마다 높이가 1씩 줄어들때, 풍선을 모두 터트릴 수 있는 최소 화살 개수를 구하는 문제이다.

❓ 문제 접근

1. 화살의 높이를 저장하여 풍선과 같은 높이에 화살이 있다면 화살의 높이를 낮추고, 그렇지 않다면 화살의 개수를 늘리는 방식으로 구현했다.
   → 공간복잡도 우선 풀이 : unordered_map STL을 사용하여 구현했다. (2156KB, 128ms)
   → 시간복잡도 우선 풀이 : 배열을 사용했더니 간결하게 코드를 구현할 수 있었다. (5804KB, 64ms)

🧠 공간복잡도 우선 풀이

#include <iostream>
#include <unordered_map>

using namespace std;

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int N,num,arrowCount = 0;
    unordered_map<int,int> arrows;
    
    cin >> N;
    
    for(int i=0; i<N; i++){
        cin >> num;
        
        unordered_map<int,int>::iterator now_iter = arrows.find(num);
        unordered_map<int,int>::iterator next_iter = arrows.find(num-1);
        
        if(now_iter != arrows.end()){
            if(now_iter->second > 1)
                arrows[num] -= 1;
            else
                arrows.erase(num);
        }
        else{
            arrowCount++;
        }
        
        
        if(next_iter != arrows.end()){
            arrows[num-1] += 1;
        }
        else{
            arrows.insert({num-1,1});
        }
    }

    cout << arrowCount << "\n";
    
    return 0;
}

🧠 시간복잡도 우선 풀이

#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int N,num,arrowCount = 0;
    int arrows[1000001];
    
    cin >> N;
    
    for(int i=0; i<N; i++){
        cin >> num;
        
        if(arrows[num])
            arrows[num]--;
        else
            arrowCount++;
        
        arrows[num-1]++;
    }

    cout << arrowCount << "\n";
    
    return 0;
}