알고리즘

[2018 KAKAO BLIND RECRUITMENT] 추석 트래픽 (Java)

suhaha 2022. 5. 6. 14:47

추석 트래픽

이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다.

 

입력 형식

  • solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다.
  • 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.sss 형식으로 되어 있다.
  • 처리시간 T 0.1s, 0.312s, 2s 와 같이 최대 소수점 셋째 자리까지 기록하며 뒤에는 초 단위를 의미하는 s로 끝난다.
  • 예를 들어, 로그 문자열 2016-09-15 03:10:33.020 0.011s은 "2016년 9월 15일 오전 3시 10분 33.010초"부터 "2016년 9월 15일 오전 3시 10분 33.020초"까지 "0.011초" 동안 처리된 요청을 의미한다. (처리시간은 시작시간과 끝시간을 포함)
  • 서버에는 타임아웃이 3초로 적용되어 있기 때문에 처리시간은 0.001 ≦ T ≦ 3.000이다.
  • lines 배열은 응답완료시간 S를 기준으로 오름차순 정렬되어 있다.

출력 형식

  • solution 함수에서는 로그 데이터 lines 배열에 대해 초당 최대 처리량을 리턴한다.

입출력 예제

예제1

  • 입력: [
    "2016-09-15 01:00:04.001 2.0s",
    "2016-09-15 01:00:07.000 2s"
    ]
  • 출력: 1

예제2

  • 입력: [
    "2016-09-15 01:00:04.002 2.0s",
    "2016-09-15 01:00:07.000 2s"
    ]
  • 출력: 2
  • 설명: 처리시간은 시작시간과 끝시간을 포함하므로
    첫 번째 로그는 01:00:02.003 ~ 01:00:04.002에서 2초 동안 처리되었으며,
    두 번째 로그는 01:00:05.001 ~ 01:00:07.000에서 2초 동안 처리된다.
    따라서, 첫 번째 로그가 끝나는 시점과 두 번째 로그가 시작하는 시점의 구간인 01:00:04.002 ~ 01:00:05.001 1초 동안 최대 2개가 된다.

 

추석 때 요청한 트래픽 배열이 들어왔을 때, 

가장 많은 트래픽이 겹친(처리한) 1초 구간을 구하는 문제이다. 

 

트래픽을 초 단위로 끊어서 하기엔 너무 많은 범위가 설정된다. 

 

트래픽이 들어왔을 때, 

 

하나의 트래픽을 기준으로

끝나는 시점 + 1초 동안 겹쳐있는 트래픽의 개수를 구하면 된다. 

 

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

class Solution {
    class Traffic {
        private Date endTime;
        private Date startTime;
        private double elapsedTime;
        
        public Traffic(Date startTime, Date endTime, double elapsedTime) {
            this.startTime = startTime;
            this.endTime = endTime; this.elapsedTime = elapsedTime;
        }
        
        public Date getStartTime() {return this.startTime; }
        public Date getEndTime() {
            return this.endTime;
        }
    }
    
    public int solution(String[] lines) {
        int answer = 1;
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
        
        try {
            List<Traffic> traffics = new ArrayList<>();
            Calendar calendar = Calendar.getInstance();
    
    		/* 트래픽 파싱 */
            for(int i = 0; i<lines.length; i++) {
                String[] tmp = lines[i].split(" ");
    
                Date end = new Date(simpleDateFormat.parse(tmp[0] + " " + tmp[1]).getTime());
                double elapsed = Double.parseDouble(tmp[2].substring(0, tmp[2].length()-1));
    
                calendar.setTime(end);
                calendar.add(Calendar.MILLISECOND, (int) -(elapsed * 1000));
                
                Date start = calendar.getTime();
                
                traffics.add(new Traffic(start, end, elapsed));
            }
            
            /* 겹친 트래픽 계산 */
            for(int i = 0; i<traffics.size()-1; i++) {
                int count = 1;
                Traffic firstTraffic = traffics.get(i);
                
                for (int j = i+1; j < traffics.size(); j++) {
                    Traffic traffic = traffics.get(j);

                    if (traffic.getStartTime().getTime() - firstTraffic.getEndTime().getTime() < 999) {
                        count++;
                    }
                }
    
                if (answer < count) {
                    answer = count;
                }
            }
            
            return answer;
            
        } catch (ParseException e) {
            e.printStackTrace();
        }
    
        return answer;
    }
}

 

문제보다 Java Date 관련 코드를 찾아보는게 더 어려웠다 

 

삽질했던 부분은

EndTime 계산을 < 1000으로 하면 될 줄 알았더니 999로 하니 통과되더라.

아마 처리시간이 0.001 이상인 것과 관련이 있는거 같은데 정확히는 모르겠다

 

그리고 시작시간 기준으로 정렬해서 풀이했는데 이렇게 하면 안되나 보다 ㅜㅜ (이유는 잘 모르겠음)

트래픽 구간합이니 세그먼트 트리 방식의 풀이도 있지 않을까 생각하는데 생각해볼 문제인거 같다.