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

1. 문제

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

프로그래머스

 

 

 

2. 풀이 과정

1. 밀리초로 변환

2. 끝나는 지점을 기준으로 정렬되어 있으므로 뒤에서부터 탐색

3. 끝나는 지점에서 1초뒤에 있는 걸 기준으로 count : 갯수가 변하는 지점이 끝나는 지점과 일치하므로

4. priority queue로 시작점이 큰 순으로 정리해놓고, 지금 보는 끝지점+1초보다 더 크면 poll()

import java.util.*;

class Solution {
    PriorityQueue<Integer> pq;

    public int getms(String[] time){
        int result = Integer.parseInt(time[0])*60;//시간 => 분
        result = (result + Integer.parseInt(time[1])) * 60;//분 => 초
        result = (result + Integer.parseInt(time[2])) * 1000;//s => ms
        result += Integer.parseInt(time[3]);
        return result;
    }

    public int solution(String[] lines) {
        pq = new PriorityQueue<>((o1, o2)->o2-o1);
        int answer = 0;
        int n = lines.length;
        StringTokenizer st = null;
        for(int i=n-1; i>=0; i--){
            st = new StringTokenizer(lines[i]);
            st.nextToken();//날짜
            String[] endTime = st.nextToken().split("[.:]");
            String[] duration = st.nextToken().split("[.s]");
            int end = getms(endTime);
            int start = end - Integer.parseInt(duration[0])*1000+1;
            if(duration.length>1){
                start -= Integer.parseInt(duration[1]);
            }
            //알고리즘
            for(int j=0, size=pq.size(); j<size; j++){
                if(end+1000>pq.peek()){
                    break;
                }
                pq.poll();
            }
            pq.add(start);
            answer = Math.max(answer, pq.size());
        }
        return answer;
    }
}