C++ 예제 (넥슨 프로그래밍 대회 문제풀이 4)

NYPC 2018 예선 5번째 문제입니다.

개인적으로 현재까지 풀어본 예선문제 중에서 가장 재미있었습니다.

최고의 동접 구간을 찾아라!

게임 분석가 승민이는 넥슨의 게임 메이플스토리가 얼마나 인기가 높은지 알고 싶어졌다. 게임의 인기는 접속한 유저 수로 알 수 있고, 특히 동시에 몇 명의 유저가 접속해 있는지를 아는 것은 게임의 인기 뿐 아니라, 게임의 관리자 입장에서도 얼마나 많은 자원을 투자해야 하는지 중요한 자료가 된다. 따라서 승민이는 가장 많은 유저들이 동시에 접속한 구간을 손쉽게 찾아내고 싶다.

넥슨은 승민이에게 유저들의 로그인 시간과 로그아웃 시간이 저장된 로그 파일을 제공했다. 여러분은 승민이를 도와서, 이 로그 파일을 이용하여 가장 많은 유저들이 동시에 접속한 구간을 찾아내는 프로그램을 작성하자.

입력 형식

첫째 줄에 로그의 수 N (1 ≤ N ≤ 300,000)가 입력된다.

다음 N 줄에 유저 하나가 로그인한 시간과 로그아웃한 시간이 공백으로 구별되어 주어진다.

• 시간은 24시간의 형태로 hh:mm, 즉 시:분의 형태로 항상 두 자리씩 주어진다.
• 로그인 시간은 로그아웃 시간보다 반드시 앞선 시간이며, 게임을 하는 동안 날짜가 바뀌는 경우는 없다.
• hh=24인 경우는 없다. 로그아웃 시간이 00:00인 경우는 주어지지 않는다.

출력 형식

가장 많은 유저가 동시에 접속한 기간을 찾아서, 먼저 이 기간에 로그인한 유저의 수를 출력한다. 다음, 이 기간의 시작 시간과 종료 시간을 각각 24시간의 형태로 hh:mm, 즉 시:분의 형태로 출력한다. 만약 이러한 기간이 둘 이상 있다면, 가장 먼저 시작한 기간을 출력한다.

입력 예제 1

5
09:00 11:20
11:00 13:50
12:00 15:00
13:00 16:20
15:50 18:45 

출력 예제 1

3
13:00 13:50

입력 예제 2

2
09:00 09:59
10:00 11:00 

출력 예제 2

1
09:00 09:59

입력 예제 3

3
01:00 08:00
02:00 03:00
03:00 05:00  

출력 예제 3

2
02:00 05:00

입출력 예제 3번의 풀이를 보다 자세히 설명하면, 다음과 같다.

• 1시부터 2시 직전까지는 1명의 유저가 로그인해 있다.
• 2시가 되면 1명의 유저가 추가로 로그인하여 동시 접속한 유저의 수는 총 2명이다.
• 이제 3시가 되면 1명의 유저가 로그아웃하는 동시에 다른 1명의 유저가 로그인하므로 동시 접속한 유저의 수는 계속해서 2명이다. 한 유저가 로그아웃하기 전 다른 유저가 로그인해서 동시 접속한 유저의 수가 3명이 되는 기간이 있거나, 한 유저가 로그아웃해서 동시 접속한 유저의 수가 1명이 된 다음 다른 유저가 로그인해서 동시 접속한 유저의 수가 다시 2명이 되는 것이 아님에 유의하시오. 따라서, 동시 접속한 유저의 수가 2명인 기간은 2시부터 5시 직전까지이다.
• 5시가 되면 1명의 유저가 로그아웃하여 동시 접속한 유저 수가 1명이 된다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

• 종류1 (10점): N ≤ 2
• 종류2 (40점): N ≤ 5,000
• 종류3 (50점): 문제의 원래 제한조건 이외의 추가된 제한이 없음.

여기까지가 문제 설명입니다.

요약하면 접속자의 로그인, 로그아웃 시간을 입력받아, 가장 많은 동시 접속자가 존재한 시간과 접속자의 수를 출력하는 문제입니다.

다만, 위 예제 3번을 자세히 살펴보면, 동시에 한사람이 나가고 한사람이 들어오면 접속자수의 변화가 없음으로 처리하고, 마찬가지로 동시에 한사람이 들어오고 나간 경우도 접속자수의 변화가 없음으로 처리되는 부분을 유의하여야 합니다.

예를 들면, 아래와 같습니다.

1. 1:00~8:00 ,현재 접속자 수 1명

2. 2:00~3:00 ,현재 접속자 수 2명 (최고 동접자 시작시간)

3. 3:00~5:00 ,현재 접속자 수 2명 (3시 동시 로그아웃, 로그인, 접속자수 변화 없음) 

따라서 최고 동접자수는 2명이며, 2명이 된 최초 시간은 2:00, 마지막 시간은 5:00 이 됩니다.

이제 C++ 코드를 살펴보겠습니다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iomanip>

using namespace std;

struct TIME_N
{
    unsigned int time;
    bool in;    
};

int getTimeInt(const string& strRec, char c)
{
    string str;
    int h=0, m = 0;
    int token = strRec.find(c);
    str = strRec.substr(0, token);
    h = atoi(str.c_str());
    str = strRec.substr(++token, strRec.length());
    m = h*60 + atoi(str.c_str());

    return m;
}

string getTimeStr(unsigned int rec, char c)
{
    stringstream ss;
    string str;
    ss << setw(2) << setfill('0') << rec / 60;
    str = ss.str();
    str.push_back(c);
    ss.str("");
    ss << setw(2) << setfill('0') << rec % 60;
    str += ss.str();
    return str;    
}

void input(int n, vector<TIME_N>& t)
{    
    for (int i = 0; i < n; i++)
    {
        string in, out;
        TIME_N tn;        
        cin >> in; // 로그인 시간        
        tn.time = getTimeInt(in, ':');
        tn.in = true;
        t.push_back(tn);

        
        cin >> out;    // 로그아웃 시간
        tn.time = getTimeInt(out, ':');
        tn.in = false;
        t.push_back(tn);
    }
}

bool sortAscending(const TIME_N& t1, const TIME_N& t2)
{
    return t1.time < t2.time;
}

int main()
{    
    int n; // 로그 개수
    cin >> n;    

    vector<TIME_N> time;
    
    input(n, time); // 로그인,아웃 시간 입력처리
    
    // 벡터 정렬
    sort(time.begin(), time.end(), sortAscending);    
 
    // 현재접속자 수, 최고동시접속자 수, 시작시간
    unsigned int user = 0, max = 0, s;    
    // 최고동접자 인덱스
    unsigned int idx = 0;
    
    for(size_t i=0; i < time.size(); i++)
    {
        if (time[i].in)
        {
            if (i > 0)
            {
                if (!time[i-1].in && time[i].time == time[i-1].time)                
                    idx = i;                
                else
                    user++;
            }
            else
                user++;
        }
        else
        {
            if (i < time.size()-1)
            {
                if (time[i+1].in && time[i].time == time[i+1].time)                
                    idx = i;                
                else
                    user--;
            }
            else
                user--;
        }        

        if (user > max)
        {
            idx = i;
            max = user;
            s = time[i].time;
        }    
    }

    // 최고동접자 끝 시간
    unsigned int e=0;

    for (size_t i = idx + 1; i < time.size(); i++)
    {
        if (!time[i].in)
        {
            e = time[i].time;
            break;
        }
    }
        
    // 결과 출력
    cout << max << endl;
    cout << getTimeStr(s, ':') << " " << getTimeStr(e, ':') << endl;
    
    return 0;
}

먼저 10번라인의 TIME_N 구조체는 시간과 그 시간이 로그인 or 아웃인지 판단하는 변수로 구성되어 있습니다.

로그인 시간이면 TIME_N 구조체의 bool 타입 변수 in 이 true 가 됩니다.

이제 66번 메인 함수로 들어가 코드를 살펴보겠습니다.

로그의 개수를 입력 받은 후, TIME_N 타입의 벡터(가변배열) time 을 선언합니다. 모든 로그인, 아웃 시간은 이 벡터에 입력받아 시간과 로그인 or 아웃 여부를 함께 저장합니다.

73번 라인 input() 함수는 로그의 개수만큼 시간을 입력받아 위에서 선언한 time 벡터에 저장합니다.

이때, 시간은 hh:mm 의 문자열 형태로 입력되므로, 이를 ':' 문자 기준으로 hh와 mm을 분리하고, hh에 60을 곱해 분단위 정수로 바꾸어 계산하기 편리하도록 저장합니다.

여기까지 코드가 수행되면 모든 로그입력이 time 벡터에 분단위 시간과 로그인 or 아웃인지 판별해 저장이 완료됩니다.

예 1)

• time[0].time = 60,  time[0].in = true  (1:00, 로그인)

• time[1].time = 480, time[1].in = false (8:00, 로그아웃)

• time[2].time = 120, time[2].in = true (2:00, 로그인)

• time[3].time = 180, time[3].in = false (3:00, 로그아웃)

이제 76번 라인에서 time 벡터를 시간기준으로 오름차순 정렬합니다.

정렬을 하는 이유는 곧 설명하겠습니다.

이제 time 벡터는 시간을 기준으로 아래와 같이 정렬됩니다.

예 2)

• time[0].time = 60,  time[0].in = true  (1:00, 로그인)

• time[1].time = 120, time[1].in = true (2:00, 로그인)

• time[2].time = 180, time[2].in = false (3:00, 로그아웃)

• time[3].time = 480, time[3].in = false (8:00, 로그아웃)

정렬 후, 로그인, 아웃 순서가 뒤죽박죽 섞이지만, 이게 의도한 대로 입니다.

왜냐하면, 정렬후 순서대로 로그인이 되면 user를 1 증가, 로그 아웃이면 1 감소시키면 최대 동시 접속자수와 최대 동접자 시작시간을 쉽게 구해낼 수 있습니다.

time 벡터를 순서대로 살펴보기 바랍니다.

예 3)

• time[0].time = 60,  time[0].in = true  (1:00, 로그인, 접속자 + 1 = 1)

• time[1].time = 120, time[1].in = true (2:00, 로그인, 접속자 + 1 = 2)

• time[2].time = 180, time[2].in = false (3:00, 로그아웃, 접속자 -1 = 1)

• time[3].time = 480, time[3].in = false (8:00, 로그아웃, 접속자 -1 = 0)

바로 최대 동시 접속자가 2명이며, 그 시작시간은 120분, 즉 2:00 이 됩니다. 

여기까지의 과정이 소스코드의 83~116번 라인 for 반복문에서 수행됩니다.

유심히 봐야 할 부분은 최대 동시접속자 수 or 시작시간은 time 벡터의 순차 탐색을 진행함에 따라 변할 수 있으므로, 110번 라인 if문에서 갱신 해야 합니다.

또한 최대 접속자가 발생한 시점의 벡터 인덱스를 저장해 둡니다.

이제 남은 것은 최대 동시접속자의 종료시간을 구하는 것입니다.

121번 라인에서 종료시간을 구합니다.

곰곰히 생각해 보면 최대 동시접속자의 종료시간은 최대 접속자수 -1 이 되는 시점이라는 것을 알 수 있습니다.

이제 아까 저장해 두었던 최대 동시접속자의 인덱스 + 1 부터 time 벡터를 탐색하며 가장 먼저 로그아웃이 일어나는 time 벡터를 찾으면 그 시간이 종료시간입니다.

이제 최대 동접자 수와 시작, 끝 시간을 알고있으므로 결과만 출력하면 끝입니다.

132번 라인의 getTimeStr() 함수는 123분으로 저장된 정수 타입 시간을 "2:03" 문자열로 변경하는 함수입니다.

마지막으로 실행파일의 수행 결과 입니다.

[입력 3번 예제 수행결과]

감사합니다.