C++ 예제 (넥슨 프로그래밍 대회 문제풀이 4)
최고의 동접 구간을 찾아라!
게임 분석가 승민이는 넥슨의 게임 메이플스토리가 얼마나 인기가 높은지 알고 싶어졌다.
게임의 인기는 접속한 유저 수로 알 수 있고, 특히 동시에 몇 명의 유저가 접속해 있는지를 아는 것은 게임의 인기 뿐 아니라, 게임의 관리자 입장에서도 얼마나 많은 자원을 투자해야 하는지 중요한 자료가 된다.
따라서 승민이는 가장 많은 유저들이 동시에 접속한 구간을 손쉽게 찾아내고 싶다.
넥슨은 승민이에게 유저들의 로그인 시간과 로그아웃 시간이 저장된 로그 파일을 제공했다.
여러분은 승민이를 도와서, 이 로그 파일을 이용하여 가장 많은 유저들이 동시에 접속한 구간을 찾아내는 프로그램을 작성하자.
입력 형식 첫째 줄에 로그의 수 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점): 문제의 원래 제한조건 이외의 추가된 제한이 없음.
#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;
}
로그인 시간이면 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, 로그아웃)
- 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)
|
| [입력 3번 예제 수행결과] |
댓글
댓글 쓰기