알고리즘/programmers

[Programmers] [1차] 추석 트래픽

꾸준함. 2022. 4. 18. 03:34

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/17676

 

코딩테스트 연습 - [1차] 추석 트래픽

입력: [ "2016-09-15 20:59:57.421 0.351s", "2016-09-15 20:59:58.233 1.181s", "2016-09-15 20:59:58.299 0.8s", "2016-09-15 20:59:58.688 1.041s", "2016-09-15 20:59:59.591 1.412s", "2016-09-15 21:00:00.464 1.466s", "2016-09-15 21:00:00.741 1.581s", "2016-09-1

programmers.co.kr

시간 전처리만 잘하면 비교적 쉽게 풀 수 있는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. lines 배열을 응답 완료 시간과 처리시간을 기준으로 전처리해준 뒤 orders 벡터에 {시작 시간, 완료 시간}을 넣어줍니다.

2. ms 단위로 슬라이딩 윈도우를 한다면 시간 초과가 발생할 것이 자명합니다.

2.1 따라서, 기준 로그의 완료시간 + 1초가 다른 로그의 시작 시간 이후라면 시간이 겹치는 것을 이용해 최대 처리량을 구해줍니다.


 

개발환경: Programmers IDE

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

반응형

'알고리즘 > programmers' 카테고리의 다른 글

[Programmers] 2 x n 타일링  (0) 2022.06.01
[Programmers] 자물쇠와 열쇠  (0) 2022.04.28
[Programmers] [1차] 셔틀버스  (0) 2022.04.15
[Programmers] 브라이언의 고민  (3) 2022.03.18
[Programmers] 양궁대회  (0) 2022.03.15