공부 기록

[프로그래머스] level 3 - 추석 트래픽 (C++) 본문

Algorithm/Programmers

[프로그래머스] level 3 - 추석 트래픽 (C++)

혜멘 2022. 2. 16. 13:58

문제 설명

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

문제 풀이

  • 추후 모든 요청의 시각을 비교하기 쉽게 하기 위해 시, 분, 초를 모두 더해 한 숫자로 나타냄.
  • 이때 istringstream 은 문자열을 공백단위로 쪼개 저장하므로 : 를 공백으로 바꾸어 시, 분, 초를 각각 나눠 저장하고, 한가지 숫자로 나타낼때 각 자릿수를 고려하여 3600, 60, 1 을 곱하여 더해줌.
  • 마지막 조건문에 +1이 아니라 +0.999 한 이유는 처리시간이 시작시간과 끝시간을 포함하기 때문
  • 완료시점이 빠른 순으로 정렬한 뒤,(사실 이미 정렬되어 있는데 문제를 제대로 안읽어서 또 정렬함. 문제 읽는게 역시 중요함) 제일 빠른 요청의 완료시각으로부터 1초 사이에 존재하는 모든 요청의 수를 구함.
  • 이때, 현재 인덱스보다 뒷 인덱스들은 모두 현재 인덱스보다 더 늦게 완료되는 요청이므로 해당 요청들의 시작시각이 현재인덱스의 완료시각 + 1초 보다 앞서 있는 것들을 구하면 됨.
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>

using namespace std;

int solution(vector<string> lines) {
    int answer = 0;
    int len = lines.size();

    double* compTime = new double[len]; // 완료시각을 모두 더하여 sec 단위로 나타낸 값
    double* procTime = new double[len]; // 처리시간 
    double hour, min, sec;

    for (int i = 0; i < len; i++) {
        lines[i][13] = lines[i][16] = ' '; // :를 공백으로 바꿔 시분초를 각각 나눠 저장함
        istringstream ss(lines[i]);
        string date;
        ss >> date >> hour >> min >> sec >> procTime[i];
        compTime[i] = hour * 3600.0 + min * 60.0 + sec;
    }

    // 완료시점이 빠른 순으로 정렬
    sort(compTime, compTime + len);
    // 현재 인덱스의 뒷 요청들의 시작시간이 현재 인덱스의 완료시점 + 1초 보다 작은 것들의 개수를 구하기
    int max;
    for (int i = 0; i < len; i++) {
        max = 1;
        for (int j = i+1; j < len; j++) {
            if (compTime[j] - procTime[j] < compTime[i] + 0.999) max++;
        }
        if (answer < max) answer = max;
    }
    return answer;
}

 

  • hour 더할때 60*60 = 3600 인데 360 해서 틀렸었음. 항상 숫자 다룰때 자릿수 주의

 

Comments