NYPC 2021 예선 | 레이스 기록 검증 풀이

[문제]

 

로그 파일이란 프로그램이 실행되면서 발생한 사건들을 기록한 파일을 의미한다. 카트라이더에서는 유저들이 레이스를 시작하고 종료하는 사건이 일어날 때마다, 어떤 시각에 어떤 유저가 레이스를 시작하거나 종료했는지에 대한 정보를 로그 파일에 기록한다. 이러한 로그 파일을 분석하면 게임 도중 발생한 에러나 부정행위 등을 찾아낼 수 있다.

예를 들어, 어떤 유저가 시작한 레이스를 종료하기도 전에 새로운 레이스를 시작했다고 로그 파일에 기록되어 있다면, 게임 프로그램에 버그가 발생했다고 의심할 수 있다. 또한, 정상적인 레이스는 1분 이상이 걸리는데, 어떤 유저가 레이스를 시작한 지 30초 만에 종료했다고 로그 파일에 기록되어 있다면, 그 유저가 정상적이지 않은 방법으로 게임을 플레이했다고 의심할 수 있다.

카트라이더에는 총 N명의 유저가 존재하며, 각각의 유저들은 1번부터 N번까지의 번호를 가지고 있다. 프로그램은 시각 0초부터 로그 파일에 정보를 기록하기 시작한다. 만약 시각 t초에 i번 유저가 레이스를 시작했다면, 로그 파일에는 t i 0이 기록된다. 만약 시각 t초에 i번 유저가 레이스를 종료했다면, 로그 파일에는 t i 1이 기록된다. 로그 파일에는 이와 같은 정보가 총 M개 존재하며, 정보들은 사건이 발생한 시간 순서대로 기록되어 있다.

여러분은 카트라이더의 로그 파일을 입력으로 받아, 로그 파일의 기록이 올바른지 확인하는 프로그램을 작성해야 한다.

 

 

[입력 형식]

 

첫 줄에 유저의 수 N과 로그 파일에 포함된 기록의 수 M이 공백으로 구분되어 주어진다. (1≤N≤100; 1≤M≤200)

둘째 줄부터 M개의 줄에 걸쳐 세 정수 t, i, s가 공백으로 구분되어 주어진다.

t는 유저가 레이스를 시작하거나 끝낸 시각을 의미한다. 시각은 초 단위이다. (0≤t<86400)

i는 유저의 번호를 나타내는 1 이상 N 이하의 정수이다. (1≤i≤N)

i번 유저가 시각 t초에 레이스를 시작했을 경우, s=0이다. i번 유저가 시각 t초에 레이스를 종료했을 경우, s=1이다.

기록은 시각(t)이 감소하지 않는 순서대로 주어진다. 또한, 같은 시각에 한 유저와 관련된 사건이 두 번 이상 일어나지 않는다. 즉, 한 유저가 레이스를 종료하는 것과 동시에 새로운 레이스를 시작하는 등의 사건은 일어나지 않는다. 단, 서로 다른 유저와 관련된 사건은 같은 시각에 일어날 수도 있다. 즉, 1번 유저가 레이스를 종료하는 것과 동시에 2번 유저가 레이스를 시작할 수 있다.

N명의 유저 중에서 로그 파일에 한 번도 등장하지 않는 유저가 있을 수 있다.

 

 

[출력 형식]

 

입력으로 주어진 로그 파일의 기록이 올바르다면 YES, 올바르지 않다면 NO를 출력한다. 출력은 대소문자를 구별하지 않는다. 즉, 만약 정답이 YES인 경우, yes나 yES를 출력해도 정답으로 인정한다.

 

 

[해설]

 

arr 배열을 만들고, 각 유저의 로그 정보를 알맞게 넣어준 다음, 문제에서 원하는 대로 그리디 하게 코드를 완성시켜주면 간단하게 풀리는 문제였습니다.

 

 

[C/C++ 코드]

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int arr[101],n,m;
bool flag;

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    fill(arr,arr+n+1,-1);
    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        if(!z){
            if(arr[y]!=-1){
            	flag=true;
            }
            arr[y]=x;
        }
        else{
            if(arr[y]==-1||x-arr[y]<60){
            	flag=true;
            }
            arr[y]=-1;
        }
    }
    for(int i=1;i<=n;i++){
    	if(arr[i]!=-1){
        	flag=true;
        }
    }
    if(!flag){
    	cout<<"YES"<<'\n';
    }
    else{
    	cout<<"NO"<<'\n';
    }
}