프로그래머스 코딩 테스트 풀이 - [1차] 추석 트래픽 (카카오 블라인드)

# 주소

https://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.001 1초 동안 최대 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초 구간은 여러 개 존재할 수 있으므로 이 문제에서는 구간이 아닌 개수만 출력한다.
  

# 문제 해설 및 코드 리뷰

import java.util.*;
class Solution{
    public int solution(String[] lines){
        int max = 0;
        List<int[]> list = new ArrayList<>();
        for(String data : lines){
            String[] temp = data.split(" ");
            String time = temp[1];
            int t = cal(time);
            String dur = temp[2];
            int d = cal2(dur);
            list.add(new int[]{t-d, 0});
            list.add(new int[]{t + 1000, 1});
        }
        list.sort(Comparator.comparingInt(a -> a[0]));
        int answer = 0;
        for(int[] data : list){
            if(data[1] == 0){
                answer++;
            }
            else
                answer--;
            max = Math.max(answer, max);
        }
        return max;
    }
    public int cal(String time){
        String[] temp = time.split(":");
        int sum = 0;
        int hour = Integer.parseInt(temp[0]);
        int min = Integer.parseInt(temp[1]);
        int sec = (int)(Double.parseDouble(temp[2]) * 1000);
        sum += 3600 * hour * 1000 + min * 60 * 1000 + sec;
        return sum;
    }
    public int cal2(String time){
        time = time.substring(0, time.length() - 1);
        int t = (int)(Double.parseDouble(time) * 1000);
        return t - 1;
    }
}

확실히 이걸 풀면서 느낀건 왜 기업에서 백준 문제보다 프로그래머스 문제를 선호하는지 알 것 같다는 느낌이었습니다.

백준은 알고리즘 연습을 하기 좋다면 프로그래머스는 실제 상황에 대한 대비를 관리 하기 쉽고 입력값을 받을 때 함수로 받기 때문에 실제 상황에 더 유사하다고 느껴집니다.

문제를 풀기 전에 먼저 생각을 해봅시다.

문제의 목표는 초단위의 프레임으로 구간을 쪼갰을 때 최대의 요청 개수를 구하는 것이 목표입니다.

이 문제를 이해하기 위해서 진짜 고생했는데 1초 단위의 개수를 구한다는 것은 그 구간동안의 변화량을 구하면 됩니다.

만약 해당 프레임마다 종료되는 지점이 있으면 --해주고 시작되는 요청이 있으면 ++해주어서 그것들을 모두 max와 비교하여 큰 값을 max에 담는 것입니다.

코드로 살펴봅시다.

List<int[]> list = new ArrayList<>();
for(String data : lines){
    String[] temp = data.split(" ");
    String time = temp[1];
    int t = cal(time);
    String dur = temp[2];
    int d = cal2(dur);
    list.add(new int[]{t-d, 0});
    list.add(new int[]{t + 1000, 1});
}

List를 선언합니다. 

List에는 int[] 타입의 배열을 담을 것입니다.

입력되는 lines값을 for문으로 돌려가며 list에 값을 넣어봅시다.

temp를 split으로 쪼갠 뒤 temp[1]과 temp[2]를 각각 연산할 것입니다.

temp[1]은 시간을, temp[2]는 구간을 의미합니다.

먼저 cal연산부터 살펴봅시다.

public int cal(String time){
    String[] temp = time.split(":");
    int sum = 0;
    int hour = Integer.parseInt(temp[0]);
    int min = Integer.parseInt(temp[1]);
    int sec = (int)(Double.parseDouble(temp[2]) * 1000);
    sum += 3600 * hour * 1000 + min * 60 * 1000 + sec;
    return sum;
}

cal연산은 갖고온 시간들을 시, 분, 초 단위로 쪼갠 뒤 모두 초단위로 나타내어 sum을 return합니다.

 

public int cal2(String time){
    time = time.substring(0, time.length() - 1);
    int t = (int)(Double.parseDouble(time) * 1000);
    return t - 1;
}

cal2연산은 구간단위인 초단위를 뒤의 s는 때 버리고 double타입의 문자를 가져온 뒤 1000을 곱하고 int로 변환합니다.

이후 전체 값에서 1을 빼고 반환합니다.

이후

list.add(new int[]{t-d, 0});
list.add(new int[]{t + 1000, 1});

list에 값을 삽입할텐데요.

문제의 설명을 잘 보시면 연산의 시작지점은 time에서 during을 빼고 1을 더한 시간부터 시작하므로 방금전 return 때 1을 뺀 것입니다.

그리고 시작 지점은 0으로 넣겠습니다.

t + 1000은 우리가 나타내는 초당 프레임을 나타내기 위함입니다. 현재의 시간에서 1초 동안에 일어나는 요청을 찾는 것이 목표이므로 t + 1000을 하여 1000씩 여유를 두겠다는 말입니다.

만약 1000을 안더하고 순수하게 시작점과 끝점을 나눈 뒤 초단위로 겹치는 부분을 찾으려면 시간 복잡도가.. 어마어마해지게 복잡해질 것입니다.

당장 1초 안에만 0.000부터 0.999까지 쪼개질 수 있으니 그것의 편차를 다 고려해서 한다면 끝도 없겠네요.

그렇다 보니 우리가 해야할 것은 시간초과가 나면 안되니까 이것의 변화량만 보고서 판단하겠다는 것입니다.

다른 예시를 들어볼게요.

여러분이 교통량을 관제하는 직원이라고 해봅시다.

이 때 초 단위가 아니라 어느 도로의 차량의 변화량을 즉각적으로 보고하고 추이하고자 한다면 그것이 가능할까요?

저로서는 절대 불가능할거라 여겨지네요.

이것을 보다 편리하게 하기 위해서 1s 단위로 현재 남아 있는 차량만 보고를 하여 변화를 추이하는 것이 훨씬더 비용절감적이지 않을까 싶습니다.

물론 실생활에선 이보다 더 느슨하게 관제할거라 여겨집니다만 차량 변화량을 전부 즉시 나타내려면 분명 과부하가 올 것입니다.

이 문제 또한 마찬가지입니다.

즉각적으로 변화를 나타내자는 것이 아니라 종료 시점에 1s씩 더해서 1s씩 끊을 때 최대로 요청하는 횟수를 찾자 이것입니다.

다음으로 넘어가봅시다.

list.sort(Comparator.comparingInt(a -> a[0]));
int answer = 0;
for(int[] data : list){
    if(data[1] == 0){
        answer++;
    }
    else
        answer--;
    max = Math.max(answer, max);
}
return max;

이후 list를 오름차순으로 정렬합니다.

그리고 answer 는 0으로 초기화하고 for문을 돌려서 data[1]의 값이 0이면 시작점을 뜻하므로 answer++를 합니다.

또한 data[1] == 1이면 종료시점을 의미하는데 이 때에는 answer--하여 줍시다.

이후 max에는 answer와 max를 비교하여 최댓값을 출력하면 정답이 되겠습니다.

 

이 문제를 가장 쉽게 이해하려면 예제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개가 된다.

여기에서 01:00:04:002 ~ 01:00:05:001사이를 1초 단위로 끊어보면 1초 내외의 기간동안 2번의 요청이 진행됨을 알 수 있습니다.

그러니까, 첫 번째 로그가 끝나고 1초도 안되어서 두 번째 로그가 기록되었다는 것을 의미합니다.

따라서 잠시나마 0.001s동안 max값은 2가 될 수 있고 곧바로 첫 번째 로그가 종료되며 answer 값은 1이 되겠지요.

이해가 어려우시면 댓글 달아주세요.

저도 이해하기 참 어려웠는데 최대한 풀어서 설명드리겠습니다.

감사합니다.