문제
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초 이내의 프로세스 count를 체크해서 최대 값을 리턴한다.
1. 문자열을 응답시간, 처리시간으로 나눈 후 요청시간, 응답시간을 밀리초로 구한다. (SimpleDateFormat, Date객체 이용)
2. req, resp 시간을 각각 최소힙에 넣어준다.
3. req, resp 를 멤버변수로 가지는 Prcoess 인스턴스를 생성하여 que에 넣어준다.
: resp가 이미 오름차순으로 정렬되어 있기 때문에 힙을 사용하지 않았다.
4. 2에서 만든 최소힙의 원소를 하나씩 꺼내면서 3에서 만든 프로세스큐의 원소가 해당 기준 시간에 속하는지 체크한다.
: 만약 프로세스큐의 원소 중 resp가 기준시간-1초 미만일 경우에는, 다음 최소힙 원소에서 더이상 체크할 필요가 없으므로 제거한다.
: 기준 시간 내에 속한다면 count를 증가시킨다.
소스코드
import java.util.*;
import java.text.*;
import java.lang.*;
class Process {
long req;
long resp;
public Process(long req, long resp){
this.req = req;
this.resp = resp;
}
public boolean ongoing(long time){
// resp가 기준 시간 -1초 이상이고, req가 기준시간 이하일 경우 해당 Process는 기준 시간 1초 이내 있는 것이므로
// true를 리턴한다.
if(resp >= time-1000+1 && req <= time) return true;
return false;
}
public boolean finished(long time){
// resp가 기준 시간-1초 미만일 경우 (+1은 시작시간, 끝시간 포함한다고 문제에 나와있으므로 더해줘야함.)
// 기준시간내 포함되지 않은 프로세스이다.
if(resp < time-1000+1) return true;
return false;
}
}
class Solution {
public PriorityQueue<Long> que;
public Queue<Process> ps;
public int maxCount = 0;
public int solution(String[] lines) throws Exception {
input(lines);
updateMaxCount();
return maxCount;
}
public void input(String[] lines) throws Exception {
ps = new LinkedList<Process>();
que = new PriorityQueue<Long>(new Comparator<Long>(){
@Override
public int compare(Long o1, Long o2){
if(o1 - o2 > 0) return 1;
else if(o1 - o2 < 0) return -1;
else return 0;
}
});
SimpleDateFormat df = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
for(int i = 0; i < lines.length; i++){
// Time으로 변환해서 첫시간, 끝시간을 PriorityQueue에 담아준다.
// 그리고 두 시간을 가지는 Process를 생성해준다.
String s = lines[i];
String date = s.substring(0, 23);
long mills = (long) (Double.parseDouble(s.substring(24).replace("s", ""))*1000);
Date d = df.parse(date);
long resp = d.getTime();
long req = resp-mills+1;
que.offer(req);
que.offer(resp);
ps.offer(new Process(req, resp));
}
}
public void updateMaxCount(){
while(!que.isEmpty()){ // 끝시간, 시작시간이 정렬되어있는 힙으로 요소를 하나씩 꺼내서 체크한다.
long time = que.poll();
int count = 0;
while(!ps.isEmpty()){
if(ps.peek().finished(time)) ps.poll();
// lines 배열이 애초에 응답시간 기준으로 오름차순이므로
// ps도 오름차순으로 쌓여있다. 때문에 이미 resp가 기준 시간-1초 미만보다 작다면
// 프로세스가 이미 종료된 것이므로 앞으로 체크하지 않기 위해 poll 해준다.
else break;
}
Iterator<Process> iter = ps.iterator();
while(iter.hasNext()){
Process p = iter.next();
// 현재 프로세스가 기준 시간 이내 ongoing중이라면 count를 증가시킨다.
if(p.ongoing(time)) count++;
}
maxCount = Math.max(maxCount, count);
}
}
}
'💡Problem Solving > Programmers' 카테고리의 다른 글
[프로그래머스] 2 x n 타일링 (Java) (1) | 2021.10.29 |
---|---|
[프로그래머스] 야근 지수 (Java) (0) | 2021.10.29 |
[프로그래머스] 문자열 압축 (Java) (0) | 2021.10.25 |
[프로그래머스] N진수 게임 (Java) (0) | 2021.10.23 |
[프로그래머스] 프렌즈4블록 (Java) (0) | 2021.10.23 |