[Java] 2018 KAKAO BLIND RECRUITMENT[1차] > 추석 트래픽: 풀이 & 코드 & 예외 상황

문제: https://programmers.co.kr/learn/courses/30/lessons/17676?language=java 

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

 

 

문제 풀이:

• 중요한 조건
  • 입력 데이터 형식: "2016-09-15 01:00:04.001 2.0s"
    • "날짜 응답완료시간 처리시간"
  • 2016년 9월 15일만 포함 
    • 날짜 무시하고 시간만 고려하면 됨
  • 처리시간은 시작 시간과 끝 시간을 포함
    • 요청의 시작 시간 = 응답완료시간 - 처리시간 + 1ms
• String 형태로 들어오는 시간은 저 상태 그대로 연산하기 불편하니 int 형으로 바꿔주었다.
  • 소수점을 없애기 위해 ms 단위로 계산
  • 최대 시간은 24:59:59.999이므로 (23*60*60*1000+59*60*1000+59*1000+999)ms이고 이는 int형을 벗어나지 않는다.
    • = 86,399,999 
    • int형 범위: ($-2^{31}$, $2^{31}-1$) 
• 시간을 int형으로 변환 후, 각 입력 데이터들을 <시작, 종료> 쌍으로 vector에 넣어준다.
• 입력 배열은 응답 완료 시간을 기준으로 정렬되어 있기 때문에 따로 정렬할 필요 없다.
  • 응답 완료 시간을 기준으로 순서대로 비교하면 된다.
• 마지막으로 각 데이터를 순환하며 가장 많이 겹치는 구간을 찾는다.
  • 현재 보는 데이터[i]의 (종료 시간[i], 종료 시간[i]+999) 구간에 다음 데이터가 포함되는지 확인
    • 조건: (종료 시간[i]+999) >= 시작 시간[j]
      • i+1 <= j <N 
      • 1000이 아니라 999를 더하는 이유는 위의 조건 확인
  • 중요!
    • 조건에서 다음 요청과 비교하는 기준은 요청 시작 시간이다
    • 종료 시간은 뒤로 갈수록 늦어지지만, 처리 시간에 따라 시작 시간은 더 빠를 수도 있다.
    • 따라서, 조건에 부합하지 않는다고 바로 break를 걸게 되면 예외 케이스에 걸리게 된다.

 

소스 코드:

public int solution(String[] lines) {
        int answer = 0;
        List<RequestTime> sections = new ArrayList<>();

        // 입력 시간을 int형 ms로 변환 및 <시작 시간, 종료 시간> 형태로 저장
        for (String line : lines) {
            sections.add(getInterval(line));
        }

        // 현재 section(종료 시간 + 999ms)과 겹치는 section 개수 카운트
        for (int i = 0; i < sections.size(); i++) {
            int count = 1;
            int right = sections.get(i).end + 999;
            for(int post=i+1; post<sections.size(); post++){
                if(right>=sections.get(post).start){
                    count++;
                }
            }
            answer = max(answer, count);
        }

        return answer;
    }

    public RequestTime getInterval(String line) {
        String[] time = line.split(" ");

        int endTime = getEndTime(time[1]);
        int startTime = getStartTime(endTime, getProcessingTime(time[2]));

        return new RequestTime(startTime, endTime);
    }

    public int getEndTime(String time) {
        String[] times = time.split(":");
        return Integer.parseInt(times[0]) * 3600000 // 시
                + Integer.parseInt(times[1]) * 60000 // 분
                + (int) (Double.parseDouble(times[2]) * 1000); // 초
    }

    public int getProcessingTime(String time) {
        String sec = Arrays.stream(time.split("s")).findFirst().get();
        double ms = Double.parseDouble(sec) * 1000;
        return (int) ms;
    }

    public int getStartTime(int endTime, int processingTime) {
        return endTime - processingTime + 1;
    }

    static class RequestTime {
        int start;
        int end;

        public RequestTime(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }