[BOJ 17952] 과제는 끝나지 않아!

문제 분석

• 2초 -Big-O 계산 약 2억
• 최근에 나온 과제부터 -> <stack> 사용
• 각 과제에는 점수와 시간 이 있음 <pair>사용

풀이 방식

• 분 마다 시행되는 과정
  
  • 과제 추가 여부 확인
  • 가장 최근 나온 과제 1분 해결
  • 만약 과제 다했으면 삭제

stack<pair<int, int>> hw;//(과제 점수,과제 하는데 걸리는시간)을 pair로 가지는 stack
int n, a, t, score;
bool exist;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    while (n--) {//n번 반복
        cin >> exist;
        if (exist) {//추가 과제 여부
            cin >> a >> t;
            hw.push({a, t});//과제 추가
        }
        if (!hw.empty()) {//과제가 없을 때에 대한 예외 처리
            hw.top().second -= 1;//가장 최근 과제 1분 어치 해결
            if (hw.top().second == 0) {//과제 끝나면
                score += hw.top().first;//점수에 추가
                hw.pop();//과제 삭제
            }
        }
    }
    cout << score;
    return 0;
}

느낀점

• 비교적 금방 풀었다. 다만 꼭 고쳐야 하는 점이 빈 stack에 접근하지 말라는 예외처리를 안했다는 점인데 이 부분은 꼭 고쳐야 겠다.
• 문제를 풀면서 <pair>를 이용하는 경우가 많다, 최근들어 자주사용하는데 알고리즘 문제 풀때 유용한 것 같다.

시간 복잡도

• stack의 top에 대한 접근, pop -> O(1)
• n번 반복
  ➣ O(n)