문제 보기 · Level 3 · 2018 KAKAO BLIND RECRUITMENT · 정답률 23% · 푼 사람 8,608명 (2026-09-30 기준)1
문제
로그 한 줄은 2016-09-15 hh:mm:ss.sss 처리시간 모양이다. 시각 S는 응답이 끝난 때이고, 처리 시간 T는 2s, 0.351s처럼 소수점 아래 셋째 자리까지 쓴다. 요청은 S − T + 0.001초부터 S까지 처리된다(양 끝 포함). 아무 1초(1,000밀리초) 구간을 잡았을 때 그 안에서 처리 중인 요청 수의 최댓값을 돌려준다.
- 로그 1~2,000개, S 순으로 정렬됨
- 0.001 ≤ T ≤ 3.000초, 시각은 밀리초 단위
풀이
막히면 한 단계씩 펼친다.
1단계 · 작은 예로 손으로 풀기
로그 두 개: 01:00:04.002 2.0s, 01:00:07.000 2s
- 첫 요청은 04.002 − 2.000 + 0.001 = 02.003초에 시작해 04.002초에 끝난다.
- 둘째 요청은 07.000 − 2.000 + 0.001 = 05.001초에 시작해 07.000초에 끝난다.
- 1초 창을 04.002 ~ 05.001로 잡으면 첫 요청의 끝과 둘째 요청의 시작이 모두 들어간다. 답은 2다.
첫 로그가 04.001에 끝났다면 창은 04.001 ~ 05.000이고, 둘째 요청(05.001 시작)은 빠진다. 답은 1이다. 이렇게 1밀리초 차이로 답이 바뀌니, 시각을 정확한 정수로 다뤄야 한다.
2단계 · 가장 단순한 방법과 그 속도
창의 시작을 하루의 모든 밀리초(8,640만 개)로 옮기며 로그 2,000개를 세면 1,700억 번이 넘는다. 안 된다.
3단계 · 핵심 아이디어
- 밀리초 정수로 바꾸기:
hh:mm:ss.sss→ (h × 3600 + m × 60) × 1000 + (초와 밀리초).04.002는 점을 빼면04002, 즉 4,002밀리초다. 처리 시간도 같은 방식으로 밀리초로 바꾼다. - 창은 어떤 요청이 끝나는 순간에 시작하면 충분하다: 가장 많이 겹치는 창을 하나 잡고 오른쪽으로 민다고 하자. 창에 걸친 요청이 빠지는 때는 창의 시작이 그 요청의 끝을 지날 때뿐이다. 그러니 창 안 요청 중 가장 먼저 끝나는 요청의 끝까지 밀어도 빠지는 요청이 없다. 새로 들어오는 요청만 생길 수 있다.
- 후보 창이 로그 수(2,000개)만큼만 있다. 후보마다 로그를 전부 세면 2,000 × 2,000 = 400만 번이다.
- 창 [e, e + 999]와 요청 [s, t]가 겹치는 조건: 요청이 창이 끝나기 전에 시작하고(s ≤ e + 999), 창이 시작한 뒤에 끝난다(t ≥ e).
4단계 · 코드 흐름
- 로그마다 끝 시각 e와 시작 시각 s = e − T + 1을 밀리초로 구한다.
- 로그마다 창 [e, e + 999]를 잡고, 겹치는 요청 수를 센다.
- 가장 큰 수를 돌려준다.
5단계 · 파이썬 코드
def to_ms(clock):
h, m, s = clock.split(":")
return (int(h) * 3600 + int(m) * 60) * 1000 + int(s.replace(".", ""))
def dur_ms(text):
sec, _, frac = text[:-1].partition(".") # '0.351s' → '0', '351'
return int(sec) * 1000 + int((frac + "000")[:3])
def solution(lines):
logs = []
for line in lines:
_, clock, dur = line.split()
end = to_ms(clock)
start = end - dur_ms(dur) + 1 # 시작과 끝 모두 포함
logs.append((start, end))
best = 0
for _, e in logs: # 창: e ~ e + 999
cnt = 0
for s2, e2 in logs:
if s2 <= e + 999 and e2 >= e:
cnt += 1
best = max(best, cnt)
return best
text[:-1]: 맨 끝 글자s를 뗀다.partition("."): 처음 나온 점을 기준으로 (앞, 점, 뒤) 셋으로 나눈다. 점이 없으면 뒤가 빈 문자열이다.'2'.partition('.')은('2', '', '')다.(frac + "000")[:3]: 소수 부분을 세 자리로 맞춘다.'0'→'000','351'→'351', 빈 문자열 →'000'.- 날짜는 모두 2016-09-15라 버린다(
_).
6단계 · 실행 추적
1단계의 두 로그를 밀리초 대신 시각으로 보인다.
| 로그 | 시작 | 끝 |
|---|---|---|
| 1 | 01:00:02.003 | 01:00:04.002 |
| 2 | 01:00:05.001 | 01:00:07.000 |
| 창 | 로그 1 겹침 | 로그 2 겹침 | 개수 |
|---|---|---|---|
| 04.002 ~ 05.001 | 끝 04.002 ≥ 04.002 | 시작 05.001 ≤ 05.001 | 2 |
| 07.000 ~ 07.999 | 끝 04.002 < 07.000, 아니다 | 겹친다 | 1 |
답은 2다.
7단계 · 복잡도와 흔한 실수
로그 N개에 \(O(N^2)\), 400만 번이다. 로그 2,000개로 재 보니 0.1초가 안 걸렸다.
- 처리 시간을
float로 바꿔 1000을 곱하고int로 자른다.int(float("1.005") * 1000)은 1004다. 실수는 1.005를 정확히 담지 못해 1004.999…가 되기 때문이다. 글자로 다루거나round를 쓴다. - 시작을 S − T로 계산한다. 양 끝을 포함하니 S − T + 0.001, 밀리초로는 e − T + 1이다.
- 창을 1,000밀리초가 아니라 1,001밀리초(e ~ e + 1000)로 잡는다. 1초 구간은 e부터 e + 999까지다.
검증: 문제의 예시 3개를 통과했고, 무작위 로그 묶음 300개에서 “창의 시작을 가능한 모든 밀리초로 옮겨 보는” 다른 풀이와 결과가 같았다. 시각 변환,
float 함정, 6단계의 시각도 계산해 확인했다 — 16_pg17676_p1.py-
프로그래머스 스쿨, “[1차] 추석 트래픽” (https://school.programmers.co.kr/learn/courses/30/lessons/17676), 2026-09-30 조회. ↩