[프로그래머스,자바] Level3: 추석 트래픽

 

문제분석

 

목표: 가장 작업이 겹치는 1초 구간 구하기

 

 

작업은 시작과 작업시간이 존재한다. 시작과 끝시간은  시간/분/초/밀리초 까지 존재한다.  

 

 

필자의 첫접근은  시간/분/초/밀리초를 10진수로 변환한뒤,

 

1ms 증가시켜 시작점을 설정한뒤 시작점+1000ms(1초)구간까지 확인했다. 

 

결과는 당연히 시간초과다.

 

사실 중간에 코딩하면서 눈치챗지만, 밀리초단위로 10진수로 변환한 수는 엄청나게크다.(약 100만)

 

이걸 100만*1000 반복시키면 당연히 시간초과가일어난다.

 

-> 조금더 효율적인 접근이필요했다.

 

그래서 카카오 해설의 도움을 빌렸다. 

 

카카오 해설의 대안은 1ms마다 탐색하지말고, 시작과 끝 경계선부분만 탐색해도 풀수있단겁니다.

https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

카카오 신입 공채 1차 코딩 테스트 문제 해설

 

이 힌트를 참고삼아 다르게 접근을했습니다.

 

우선 하나의 List에  작업의 시작점과 상태를넣습니다.

 

new int[] {시작 시간, 상태(0 : 시작)}

 

그후, List에 작업의 종료점을 넣습니다.

 

new int[]{종료시간, 상태(1:종료)}  

여기서 종료시간에 +1000을 해줍니다.

 

-> 그 이유는 1초 구간때문입니다.

 

EX)  100~150 까지 처리하는 작업 A가 있다고 가정합시다.

 

100에서 1초구간(1000)을 탐색하면 1100까지 작업A를 처리하는 구간입니다. 

그렇다면 149에서 1초구간(1000)을 탐색하면 1149까지 작업 A를 처리하는 구간도 역시 맞습니다.

 

즉, 1초구간으로 탐색하는 작업 A는 실제로 100~1149까지 작업구간이라고 생각해도 됩니다. (종료 1150)

 

 

문제풀이

 

 

시간을 계산하는 메소드다

 

cal은  time을 변환

 

cal은 처리작업시간을 변환한다.

 

 

기록들을 순회하면서, 리스트에 {시작점 , 시작상태(0)} 과 {종료점, 종료상태(1)}을 넣는다.

 

 

이 기록들을  시간순대로 다시 재배열 시킨다.

 

그 후, 리스트의 상태를 탐색한뒤 

 

작업시작이면 +1, 작업이 종료대면 -1를 한다.

최고점을 찍은 점수를 저장해둔다.

 

전체코드:

import java.util.*;
class Solution {
    public int solution(String[] lines) {
        int max = 0;
        List<int[]> list = new ArrayList<>();
        for(String data:lines){
            String[] temp =data.split(" ");
            String time=temp[1];
            int t=cal(time);
            String dur=temp[2];
            int d=cal2(dur);
            list.add(new int[]{t-d,0});
            list.add(new int[]{t+1000,1});
        }
        
        Collections.sort(list,(a,b)->(a[0]-b[0]));
        int cnt=0;
        
        for(int[] data:list){
            if(data[1]==0){
                cnt++;
            }
            else{
                cnt--;
            }
            max=Math.max(max,cnt);
        }              
        return max;
    }
    
    public int cal(String time){
        String[] temp = time.split(":");
        int sum=0;
        int hour=Integer.parseInt(temp[0]);
        int min=Integer.parseInt(temp[1]);
        int sec=(int)(Double.parseDouble(temp[2])*1000);
        
        sum+=3600*hour*1000+min*60*1000+sec;
        return sum;
    }
    public int cal2(String dur){
        dur=dur.substring(0,dur.length()-1);
        int time=(int)(Double.parseDouble(dur)*1000);
        return time-1;
    }
}