프로그래머스 - 추석 트래픽(01/23) (java)

1. 문제

programmers.co.kr/learn/courses/30/lessons/17676

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

문제 설명

이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 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.0011초 동안 최대 2개가 된다.

예제 3

• 입력: [
  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
  ]

• 출력: 7

• 설명: 아래 타임라인 그림에서 빨간색으로 표시된 1초 각 구간의 처리량을 구해보면(1)은 4개,(2)는 7개,(3)는 2개임을 알 수 있다. 따라서초당 최대 처리량은 7이 되며, 동일한 최대 처리량을 갖는 1초 구간은 여러 개 존재할 수 있으므로 이 문제에서는 구간이 아닌 개수만 출력한다.

  

---

2. 어떻게 풀까?

• 입력으로 주어진 응답 완료 시간과 처리 시간을 이용하여 응답 시작 시간을 구한다.

• 시작 시간, 완료 시간을 구간 시작으로 저장하여 1초동안 처리하는 데이터를 찾는다.

  • 구간에서 처리하고 있는 데이터는

    1. 응답 시작 시간이 구간에 걸쳐있는 경우

    2. 응답 완료 시간이 구간에 걸쳐있는 경우

    3. 응답 시작 시간 ~ 응답 완료 시간 사이에 구간이 포함되는 경우

• 가장 많은 데이터 처리량을 구한다.

---

3. 코드

테스트 코드

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

  @Test
  public void test1() {
    String[] lines = {
        "2016-09-15 01:00:04.001 2.0s",
        "2016-09-15 01:00:07.000 2s"
    };
    assertThat(new Solution().solution(lines), is(1));
  }

  @Test
  public void test2() {
    String[] lines = {
        "2016-09-15 01:00:04.002 2.0s",
        "2016-09-15 01:00:07.000 2s"
    };
    assertThat(new Solution().solution(lines), is(2));
  }

  @Test
  public void test3() {
    String[] lines = {
        "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"
    };
    assertThat(new Solution().solution(lines), is(7));
  }
}

실제 코드

import java.util.ArrayList;
import java.util.List;

public class Solution {

  private List<Integer> starts;
  private List<Integer> startTimes;
  private List<Integer> endTimes;

  public Solution() {
    starts = new ArrayList<>();
    startTimes = new ArrayList<>();
    endTimes = new ArrayList<>();
  }

  public int solution(String[] lines) {
    timeToMilliseconds(lines, starts, startTimes, endTimes);
    int max = 0;

    for (int startSection : starts) {
      int endSection = startSection + 1000;
      max = Math.max(max, getProcessCount(startSection, endSection));
    }

    return max;
  }

  private int getProcessCount(int startSection, int endSection) {
    int count = 0;
    for (int i = 0; i < startTimes.size(); i++) {
      if (isPartOfSection(startSection, endSection, startTimes.get(i), endTimes.get(i))) {
        count++;
      }
    }
    return count;
  }

  private boolean isPartOfSection(int startSection, int endSection, int startTime, int endTime) {
    return (startTime >= startSection && startTime < endSection)
        || (endTime >= startSection && endTime < endSection)
        || (startTime <= startSection && endTime >= endSection);
  }

  private void timeToMilliseconds(String[] lines, List<Integer> starts, List<Integer> startTimes,
      List<Integer> endTimes) {
    for (String line : lines) {
      String[] log = line.split(" ");
      int endTime = getSeconds(log[1]);
      int processTime = (int) (Double.parseDouble(log[2].replace("s", "")) * 1000);
      int startTime = endTime - processTime + 1;
      startTimes.add(startTime);
      endTimes.add(endTime);
    }
    starts.addAll(startTimes);
    starts.addAll(endTimes);
  }

  private int getSeconds(String time) {
    String[] split = time.split(":");
    return (Integer.parseInt(split[0]) * 60 * 60 * 1000)
        + (Integer.parseInt(split[1]) * 60 * 1000)
        + (int) (Double.parseDouble(split[2]) * 1000);
  }
}

• timeToMilliseconds()에서 입력으로 주어진 lines를 통해 응답 시작 시간과 완료 시작을 구하고, 각 startTimes, endTimes에 저장한다. 그리고 구간 시작점 starts를 따로 만들어 저장한다.

  • lines에서 완료 시간과 처리시간을 추출하고, HH:mm:ss.sss로 주어진 완료 시간을 getSeconds()에서 밀리 초로 환산해서 List에 저장한다.

• starts에 저장된 구간 시작 지점을 반복문을 통해 구간을 만들고 getProcessCount()에서 구간 내에 처리량을 구한다.

---

4. 느낀 점

• "각 응답의 시작점과 끝점을 구간으로 잡아야겠다"라는 생각을 하기까지 시간이 좀 걸렸다. 위에 그림처럼 직접 그림을 그려서 정리를 하니까 그 생각이 들었다.

• "응답의 시작점과 끝점을 세트로 묶어야겠네?"라는 생각으로 처음에는 Entry가 필요하겠구나 생각했는데 Entry에 추가하는 메서드가 없어서 Map으로 구현하여 Key, Value -> 시작점, 끝점을 저장했다.

  • 근데 계속 틀려서 왜 틀리는지 생각을 해봤는데, Map의 Key값, 즉 시작점이 같아지는 경우가 있을 수 있는 걸 생각하지 못했다. 그러면 Map에 data를 추가하는 것이 아닌, 교체하는 것이 되기 때문에 적절한 자료구조를 사용하지 못한 것이라고 볼 수 있다.

  • 그래서 List로 다시 구현했다.

• 처음 시간을 계산할 때 LocalTime 클래스를 사용하려 했다. 근데 코드를 작성할수록 더 복잡해지는 것 같아서 시간을 밀리 초로 환산하는 메서드를 만들어서 해결했다.

• 처음에 최대 처리량을 max를 Integer.MIN\_VALUE로 초기화했는데, 계속 틀렸다. 당연하지만 첫 최대 처리량을 0으로 초기화했어야 했다.

• level2보다 level 3가 확실히 어려운데, 연습을 계속하면 할 만한 것 같기도 하다.