게임 서버 세션 분석

문제

온라인 게임 서버의 하루치 접속 로그가 문자열 배열 logs로 주어집니다. 각 로그는 다음 형식입니다.

"HH:MM userId ACTION"

• HH:MM — 이벤트 발생 시각 (00:00 ~ 23:59)
• userId — 영문 소문자·숫자로 이루어진 유저 식별자
• ACTION — IN(로그인) 또는 OUT(로그아웃)

서버는 다음 규칙으로 세션 을 관리합니다. (시간 단위는 모두 분)

1. IN은 그 시각에 새 세션을 시작합니다.
2. OUT은 열려 있는 세션을 종료합니다. 단, 로그인 후 limit분이 지나도록 로그아웃이 없으면 세션은 로그인 시각 + limit분에 자동 종료 된 것으로 봅니다. 즉 세션 종료 시각은 min(로그인 시각 + limit, OUT 시각)입니다.
3. 열려 있는 세션이 있는 상태에서 같은 유저의 IN이 다시 오면, 기존 세션을 min(로그인 시각 + limit, 새 IN 시각)에 먼저 종료하고 새 세션을 시작합니다.
4. 열려 있는 세션이 없는 유저의 OUT은 무시합니다.
5. 하루가 끝날 때(24:00)까지 종료되지 않은 세션은 min(로그인 시각 + limit, 24:00)에 종료된 것으로 봅니다.

세션의 접속 시간은 종료 시각 - 시작 시각(분)이며, 유저는 시작 시각(포함)부터 종료 시각(미포함)까지 접속 중인 것으로 셉니다.

solution(logs, limit, k)를 구현해 다음을 담은 문자열 배열을 반환하세요.

• 첫 번째 원소: 동시 접속자 수가 최대가 되는 가장 이른 시각 을 "HH:MM" 형식으로.
• 이후 원소: 총 접속 시간(모든 세션 합)이 1분 이상 인 유저 중 상위 k명의 userId. 총 접속 시간 내림차순, 같으면 userId 사전순 오름차순. 대상 유저가 k명 미만이면 있는 만큼만 반환합니다.

예시

예시 1

logs = ["09:00 alice IN", "09:10 bob IN", "09:20 alice OUT", "09:30 bob OUT"]
limit = 60, k = 1
결과: ["09:10", "alice"]

09:10~09:19에 alice·bob 2명이 동시 접속(최대). 총 접속 시간은 alice 20분, bob 20분으로 동점이므로 사전순으로 alice가 1위.

예시 2

logs = ["10:00 carol IN", "11:30 carol OUT"]
limit = 60, k = 1
결과: ["10:00", "carol"]

carol은 10:00에 로그인했지만 60분이 지나도록 로그아웃하지 않아 세션이 11:00에 자동 종료됩니다(접속 60분). 11:30의 OUT은 이미 종료된 세션이므로 무시됩니다.

예시 3

logs = ["08:00 neo IN", "08:30 trin IN", "08:40 neo IN", "09:00 trin OUT"]
limit = 50, k = 2
결과: ["08:30", "neo", "trin"]

neo의 첫 세션은 08:40의 재로그인으로 08:40에 종료(40분), 두 번째 세션은 로그아웃이 없어 09:30에 자동 종료(50분) → 총 90분. trin은 08:3009:00 → 30분. 08:3008:59에 2명 동시 접속이 최대입니다.

제약 조건

• 1 ≤ logs.length ≤ 100,000
• 로그는 시각 오름차순으로 주어지며, 같은 시각의 로그는 배열에 나온 순서대로 처리합니다.
• userId는 영문 소문자·숫자 1~10자.
• 1 ≤ limit ≤ 1440, 1 ≤ k ≤ 100
• 접속 시간이 1분 이상인 유효한 세션이 최소 하나 존재합니다.

시간 복잡도 목표: O(N + U log U) (N = 로그 수, U = 유저 수)