[그리디] 추석 트래픽 - 2018 카카오 블라인드 채용

해결 방법

프로그래밍 언어로는 날짜 계산에 익숙한 Java를 선택했다.

요청 날짜가 밀리초(millis)까지 표시되므로, 두 날짜의 차이는 두 Date 객체의 getTime() 값의 차이로 구할 수 있다.

getTime()은 지정된 시간을 long 타입의 밀리초로 표시한다.

그리고, 처리시간은 시작시간과 끝시간을 포함하므로, 측정 범위에서 끝시간-시작시간=999ms가 된다는 점을 기억해두자.

 

날짜 계산은 이렇게 하는걸로 하고, 이제 요청 i와 요청 j가 1초 간격 내에 포함되는가를 따져봐야 한다.

먼저, 요청 i의 왼쪽점 기준으로 따져봐야 한다.

요청 i의 왼쪽점 기준으로 요청 i와 요청 j가 1초 간격 내에 포함되는 경우는 다음과 같다.

위 4가지 경우는 3가지 조건으로 다음과 나타낼 수 있다.

-> (ai-999<=aj<=ai) 또는 (ai-999<=bj<=ai) 또는 (aj<=ai-999, bj>=ai)

aj, bj가 모두 ai보다 큰 경우는, 요청 j가 기준인 반복 주기에서 요청 i를 반영할 것이니 신경쓰지 않아도 된다.

 

다음은 요청 i의 오른쪽점 기준이다.

그리고 위의 경우는 다음과 같이 나타낼 수 있다.

-> (bi<=aj<=bi+999) 또는 (bi<=bj<=bi+999) 또는 (aj<=bi, bj>=bi+999)

 

 

소스 코드

위 해결 방식을 코드로 옮긴다면 다음과 같이 구현할 수 있다.

import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.*;

class Solution {
    List<Date> a = new ArrayList<>();
    List<Date> b = new ArrayList<>();
    
    public int solution(String[] lines) {
        int answer = 0;
        long ai, aj, bi, bj;
        String start, end, line;
        String[] sp;
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
        Date sdate, edate;
        Calendar cal = Calendar.getInstance();
        for(int i=0;i<lines.length;i++){
            line=lines[i];
            sp=line.split(" ");
            try{
                edate=sdf.parse(sp[0]+" "+sp[1]); // sp[0] : yyyy-MM-dd, sp[1] : HH:mm:ss.SSS
                b.add(edate); // 각 요청의 오른쪽점(끝시간)인 b 저장 
                cal.setTime(edate);
                int ptmilli = (int) (Float.parseFloat(sp[2].split("s")[0])*1000);
                cal.add(Calendar.MILLISECOND, -ptmilli+1); // 요청의 시작시간 구하기
                sdate=sdf.parse(sdf.format(cal.getTime()));
                a.add(sdate); // 각 요청의 왼쪽점(시작시간)인 a 저장
            } catch(Exception e){e.printStackTrace();}
        }
        
        int cnt;
        for(int i=0;i<lines.length;i++){
            ai=a.get(i).getTime();
            bi=b.get(i).getTime();
            cnt=0;
            for(int j=0;j<lines.length;j++){
                aj=a.get(j).getTime();
                bj=b.get(j).getTime();
                if((aj>=(ai-999)&&aj<=ai)||(bj>=(ai-999)&&bj<=ai)||(aj<=(ai-999)&&bj>=ai)) cnt++;
            }
            if(answer<cnt) answer=cnt;
            
            cnt=0;
            for(int j=0;j<lines.length;j++){
                aj=a.get(j).getTime();
                bj=b.get(j).getTime();
                if((aj>=bi&&aj<=(bi+999))||(bj>=bi&&bj<=(bi+999))||(aj<=bi&&bj>=(bi+999))) cnt++;
            }
            if(answer<cnt) answer=cnt;
        }
        return answer;
    }
}

 

테스트케이스 22개 모두 정답