백준[14864] - 줄서기

문제

백준 14864 문제 보기

접근 방법

문제를 손으로 적어보고 그대로 구현해보니깐 정답이 나왔다. 그래도 초반 몇번의 제출에서는 시간 초과가 나왔는데 벡터를 사용하는 대신 배열을 사용해서 시간 초과가 났다. 이유는 중간을 지웠을 경우 중간 인덱스서 부터 맨끝까지 한 칸씩 앞으로 땡겨야 했다.
문제 접근은 처음 입력을 받으면서 나보다 뒤에 몇명이 작은 숫자를 들고 있는지 확인한다. 즉, (1,2),(1,3)이 입력이 될 경우 1 학생 입장에서는 자신 보다 뒤에 서고 작은 숫자를 들고 있는 사람이 2명이다. 따라서 strArr[1] = 2 이다.
그리고 카드 벡터에서 1 학생 입장에서 자신 보다 작은 숫자가 2개 있으므로 3 번째 작은 숫자를 뽑고 erase한다. 이런식으로 배열을 만든 뒤 모든 입력쌍과 학생들이 들고 있는 카드의 배열이 맞는지 확인한다.

코드

#include <iostream>
#include <utility>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int N, M;
int student[100001];
int stdArr[100001];
vector<int> card;
pair<int, int> arr[1000001];

int check() {

    for(int i = 1; i <= M; i ++) {
        int x = arr[i].first;
        int y = arr[i].second;

        if(student[x] < student[y]) {
            return -1;
        }
    }
    return 1;
}

int main() {

    cin >> N >> M;

    memset(stdArr, 0, sizeof(stdArr));

    for(int i = 1; i <= N; i ++) {
        card.push_back(i);
    }

    for(int i = 1; i <= M; i ++) {
        int a, b;

        cin >> a >> b;

        stdArr[a]++;
        arr[i].first = a;
        arr[i].second = b;
    }

    if(N == 1) {
        cout << 1;
        return 0;
    }

    for(int i = 1; i <= N; i ++) {
        int cardT = stdArr[i];

        student[i] = card[cardT];
        card.erase(card.begin() + cardT);
    }

    int chk = check();

    if(chk == 1) {
        for(int i = 1; i <= N; i ++) {
            cout << student[i] << " ";
        }
    } else {
        cout << -1 << endl;
    }
    return 0;
}