카카오 신입 공채 1차 코딩 테스트 문제 7. 추석 트래픽(난이도: 상)

카카오 블라인드 채용에 출제된 문제가 공개돼 풀어보았다. 한 문제당 하나의 클래스로 만들었으며 테스트 코드까지 한꺼번에 올린다. 실제 채용 시험의 채점이 어떻게 이뤄졌는지 모르지만, 문제에 나와있는 입출력은 모두 만족하는 코드이다. 강의할 때도 늘 말하는 것이지만, 코드에 정답은 없다. 문제를 푸는 하나의 방법이 될 수 있음을 기억하고 참고하라.

문제 7. 추석 트래픽(난이도: 상)

문제 설명과 해설은 아래 링크를 참고하라.

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

이 문제를 풀면서 느낀 점은 문제의 요구사항이 불필요하게 복잡하다는 것이었다. 2초 동안 처리하여 7.000초에 끝난 작업은 5.001초에 시작한 것이라고 일부로 복잡하게 문제를 만들어 놓은 느낌이다. 이 문제의 해결은 초당 최대 처리량을 구하기만 하면 되는 것인데, 잘 생각해 보면 어떠한 작업이 시작할 경우에만 처리량이 늘어난다. 따라서 모든 작업이 시작하는 각각의 시점을 기준으로 1초 전부터 처리한 작업의 양을 계산 한다면 최대 처리량을 구할 수 있다. 이 문제를 쉽게 해결하기 위해서 모든 시간 정보를 정수 형식으로 변환해 계산하였다. 1차 시도에서는 소수점을 그대로 사용하면서 계산을 했더니 부동소수점의 체계의 문제 때문에 정확한 시간 계산을 할 수 없었다. 그리하여 바로 모든 시간을 정수 형태로 바꿔서 문제를 풀었다. 

import org.junit.Test;
 
import static org.junit.Assert.assertEquals;
 
public class Q7 {
    public static void main(String[] args) {
    }
 
    @Test
    public void question7_TC1() {
        String[] line = {
                "2016-09-15 01:00:04.001 2.0s",
                "2016-09-15 01:00:07.000 2s"
        };
 
        assertEquals(1, question7(line));
    }
 
    @Test
    public void question7_TC2() {
        String[] line = {
                "2016-09-15 01:00:04.002 2.0s",
                "2016-09-15 01:00:07.000 2s"
        };
 
        assertEquals(2, question7(line));
    }
 
    @Test
    public void question7_TC3() {
        String[] line = {
                "2016-09-15 20:59:57.421 0.351s",
                "2016-09-15 20:59:58.233 1.181s",
                "2016-09-15 20:59:58.299 0.8s",
                "2016-09-15 20:59:58.688 1.041s",
                "2016-09-15 20:59:59.591 1.412s",
                "2016-09-15 21:00:00.464 1.466s",
                "2016-09-15 21:00:00.741 1.581s",
                "2016-09-15 21:00:00.748 2.31s",
                "2016-09-15 21:00:00.966 0.381s",
                "2016-09-15 21:00:02.066 2.62s"
        };
 
        assertEquals(7, question7(line));
    }
 
 
    public int question7(String[] line) {
 
        int[][] total = new int[line.length][2];
 
        for (int i = 0; i < line.length; i++) {
 
            String s = line[i];
 
            if (s.length() < 1 || s.length() > 2000) return -1;
 
            int hh = 0;
            int mm = 0;
            int ss = 0;
 
            String[] tempLog = s.split(" ");
            String[] tempTime = tempLog[1].split(":");
 
            hh = Integer.parseInt(tempTime[0]) * 1000;
            mm = Integer.parseInt(tempTime[1]) * 1000;
            ss = (int) (Double.parseDouble(tempTime[2]) * 1000.0);
 
            total[i][0] = (hh * 60 * 60) + (mm * 60) + ss;
            total[i][1] = (int) (Double.parseDouble(tempLog[2].replace("s", "")) * 1000.0);
        }
 
        int maxTraffic = 0;
 
        for (int i = 0; i < total.length; i++) {
            int tempTraffic = 0;
 
            for (int j = 0; j < total.length; j++) {
                if (total[i][0] - total[i][1] + 1 - 999 <= total[j][0] - total[j][1] + 1 &&
                        total[i][0] - total[i][1] + 1 >= total[j][0] - total[j][1] + 1) {
                    //j의 시작 시간이 i의 시작 시간 1초 내
                    tempTraffic++;
                } else if (total[i][0] - total[i][1] + 1 - 999 <= total[j][0] &&
                        total[i][0] - total[i][1] + 1 >= total[j][0]) {
                    //j의 종료 시간이 i의 시작 시간 1초 내
                    tempTraffic++;
                } else if (total[i][0] - total[i][1] + 1 - 999 > total[j][0] - total[j][1] &&
                        total[i][0] - total[i][1] + 1 < total[j][0]) {
                    //j의 실행시간이 i의 시작-1~시작 시간을 포함
                    tempTraffic++;
                }
            }
 
            if (maxTraffic < tempTraffic)
                maxTraffic = tempTraffic;
        }
 
 
        return maxTraffic;
    }
 
 
}