[프로그래머스] 추석 트래픽 (Java)

문제

https://programmers.co.kr/learn/courses/30/lessons/17676#

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

풀이

변경이 일어난 시간 마다 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);
        } 
    }
}