글 읽기 - 7662 질문드립니다 (코드 주석 적어둡니다!)

y00n_nms 4년 전 0

최대힙과 최소힙을 만들어서 각각 넣고, ind로는 인덱스로 해당 원소가 유효한지 아닌지 판단했습니다.

잘못된 부분이나 반례 찾아주시면 감사하겠습니다 ㅠㅠ

using namespace std;
typedef long long ll;

int T;
int t;
char n;
int morn;
ll num;


void check() {
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, less<>> max_heap;   //최대힙
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> min_heap;   //최소힙
    pair<ll, ll> p; //숫자, cnt(몇번째 숫자)
    int ind[1000001] = {0, }; //0이면 있는거, 1이면 없는거
    ll size = 0; //유효한 원소의 사이즈
    ll cnt = 0; //숫자의 번호
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n;
        if (n == 'I') { //입력
            cin >> num;
            max_heap.push(make_pair(num, cnt)); //최대힙과 최소힙에 넣음
            min_heap.push(make_pair(num, cnt));
            size++;
            cnt ++;
        } else if (n == 'D') {
            cin >> morn;
            if (size == 0) { //비어있으면 
                continue;
            }
            if (morn == 1) { //최대값 삭제
                while (1) { //최대힙의 top이 유효하지 않으면 pop 
                    if (ind[max_heap.top().second] == 1) {
                        max_heap.pop();
                    } else break;
                }
                p = max_heap.top(); //최대힙의 top 삭제 후 ind에서 삭제
                if (ind[p.second] == 0) {
                    max_heap.pop();
                    ind[p.second] = 1;
                    size--;
                }
            }


            if (morn == -1) { //최소값 삭제

                while (1) { //최소값의 top이 유효하지 않으면 pop
                    if (ind[min_heap.top().second] == 1) {
                        min_heap.pop();
                    } else {
                        break;
                    }
                }

                p = min_heap.top(); //최소힙의 top 삭제 후 ind에서 삭제
                if (ind[p.second] == 0) {
                    min_heap.pop();
                    ind[p.second] = 1;
                    size--;
                }
            }
        }

    }
    if (size == 0) {
        cout << "EMPTY" << endl;
    }
    if(size > 0){
        cout << max_heap.top().first << " " << min_heap.top().first<<endl;
    }
}

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

    cin >> T;

    for(int i = 0; i<T; i++){
        check();
    }
}

park780172 4년 전 0

최종 결과를 출력하기 전에 유효하지 않은 값이 나올 수도 있을 것 같습니다.

그리고 while(1) 안에서 pop() 후에는 비어 있을 수도 있는데, top().second로 접근해버리면 오류가 발생할 수도 있습니다.

y00n_nms 4년 전 0

댓글 감사합니다.

if (size == 0) { //비어있으면

continue;

}

부분으로 유효한 원소개수를 확인하기 때문에 유효하지 않은 것들을 pop 한 후에는 유효한 것이 최소한 하나는 남아있을 것 같은데 제가 잘못 생각하고 있는 건가요?

tothesky7 4년 전 1

앞선 답변자님께서 말씀하신 "최종 결과를 출력하기 전에"의 뜻은 70-72번째 줄에서 최종 결과를 출력할 때

max_heap.top().second == 0임이 보장되지 않았다는 뜻인 것 같습니다. (min_heap도 마찬가지)

해당 코드 직전에도 max_heap & min_heap의 top().second가 1일 경우 pop()을 반복하는 코드를 추가해주셔야 할 겁니다.

간단한 반례도 함께 첨부해 드립니다!

1
3
I 1
D 1
I 2

// Expected Answer: 2 2

y00n_nms 4년 전 0

감사합니다 !! 골드 문제 막 시작했는데 역시 어렵네요.. :>

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

7662 질문드립니다 (코드 주석 적어둡니다!)

y00n_nms 4년 전 0

park780172 4년 전 0

y00n_nms 4년 전 0

tothesky7 4년 전 1

y00n_nms 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말