[programmers/kakao] 코딩테스트 - 추석 트래픽 (Java)

문제

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

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

작년 추석 트래픽을 보고 초당 최대 처리량을 구하려고한다.

초당 최대 처리량은 응답 성공 여부와 관계없이 요청을 받아들이는 기준이다.

입력이 주어질때, 1초 초당 최대 처리량을 구하는 문제다.

---

풀이

완전탐색으로 풀리는 문제다. 탐색과 입력 로그를 파싱한 방법?에 따라서 1초에 포함되는지 여부를 O(N*(N/2))에 구할수 있다. N이 최대 2,000이므로 완전탐색으로 풀린다.

 

아이디어

1. 로그의 시,분,초를 초로 환산한 후, 시작시간과 끝나는 시간을 각각 저장한다. 

2. 그 후, 저장된 로그를 탐색하며, 최대 포함 로그 횟수를 구하면 된다.

 

1번 아이디어를 떠올리냐 못떠올리냐에 따라서 문제 난이도가 크게 달라지는 문제였다고 생각한다.

로그를 초로 환산하지 않고 포함여부를 판단해도 풀리긴할것으로 예상되는데, 이 경우 파싱이 너무 어렵다.

 

예를들어, 끝나는 시간이 12:00:00.000 이고, 처리 시간이 2.0s이라면, 시작시간은 11:59:58.001 이 된다. 즉, 처리시간 2.0s를 계산해주기 위해서 시, 분을 거슬러 올라가야한다. 반면, 시, 분, 초를 모두 초로 환산해보자.

12시 는 12 * 3600 으로 환산되며,

00분은 00 * 60 으로 환산된다.

마지막 초까지 전부 더한후 처리시간 2초를 빼주면, 표현법이 훨씬 간단해진다.

(초가 소수점 셋제자리까지 나오기 때문에, 1,000을 곱해줬다. 헷갈리면 double로 해도 무방함)

 

핵심구현

Log 클래스

    private static class Log {
        
        private long startSeconds;
        private long endSeconds;
        
        public boolean isLogIncluded(Log includedLog){
            if(this.endSeconds + 1000 > includedLog.getStartSeconds()) return true;
            return false;
        }
        
        public long getStartSeconds(){
            return this.startSeconds;
        }
        
        public long getEndSeconds(){
            return this.endSeconds;
        }
        
        public Log(String logLine){
            String[] splitedLogLine = logLine.split(" ");
            String date = splitedLogLine[1];
            String operationTime = splitedLogLine[2];
            this.parseEndSeconds(date, operationTime);
        }
        
        private void parseEndSeconds(String date, String operationTime){
            String[] times = date.split(":");
            long hourSeconds = Long.parseLong(times[0])*3600 * 1000L;
            long minuteSeconds = Long.parseLong(times[1])*60 * 1000L;
            long seconds = (long)(Double.parseDouble(times[2]) * 1000L);
            this.endSeconds = hourSeconds + minuteSeconds + seconds;
            this.parseStartSeconds(hourSeconds + minuteSeconds + seconds, operationTime);
        }
        
        private void parseStartSeconds(long endSeconds, String operationTime){
            long operationSeconds = (long)(
                Double.parseDouble(operationTime.substring(0, operationTime.length()-1))
                *1000L);
            this.startSeconds = (endSeconds-operationSeconds)+1;
        }
        
    }

Log를 갖고 포함여부를 계산하는 클래스

    private int calcOperationOfSeconds(List<Log> logs){
        int operationCount = 0;
        for(int i = 0; i < logs.size(); i++){
            Log standardLog = logs.get(i);
            int tempOperationCount = 1;
            for(int j = i+1; j < logs.size(); j++){
                if(!standardLog.isLogIncluded(logs.get(j))) continue;
                tempOperationCount++;
            }
            operationCount = max(operationCount, tempOperationCount);
        }
        return operationCount;
    }

---

전체소스코드

https://github.com/devxb/JJUNalgo/blob/master/programmers%20%EC%B6%94%EC%84%9D%20%ED%8A%B8%EB%9E%98%ED%94%BD/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃