코딩테스트 -- [1차] 추석 트래픽 - (프로그래머스 / C++)

 

코딩테스트 연습 - [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

---

 

네... 바로 이해 못 했습니다...

but! 몇 번 읽어 보니 대충 

1. 데이터 처리완료 시간과 실행시간을 준다

2. 1초 단위로 쪼개어 데이터 처리기간이 겹치는 부위를 찾고

3. 그 부위에서의 데이터량에 대해서 최댓값을 찾아 출력!

 

프로그래머스 참고그림

 

문제 아래에 그림을 보니 훨씬 이해하기 편하네요

 

일단 시작해볼게요!

 

먼저 문자열을 시간, 분, 초, 밀리초에 따라 나누어 받아봅시다.

for(int i=0;i<lines.size();i++){
        int sum=0;
        sum+=stoi(lines[i].substr(11,2))*60*60*1000;
        sum+=stoi(lines[i].substr(14,2))*60*1000;
        sum+=stoi(lines[i].substr(17,2))*1000;
        sum+=stoi(lines[i].substr(20,3));

문자열을 자르는 함수 substr(시작, 글자 수)를 통해 자르고

저는 모두 밀리 초로 변경시켜 다 더해주도록 하겠습니다.

 

다음은 실행시간인데 여기에 s라는 문자가 하나 붙어 있어서 어디까지 자를지 찾은 후 잘라보았습니다.

int count=0;
        for(int j=0;j<5;j++){
            count+=1;
            if(lines[i][24+j]=='s'){
                count-=1;
                break;
            }
        }
        timers[i][0]=sum-stof(lines[i].substr(24,count))*1000+1;//시작시간
        timers[i][1]=sum;//끝

시간 계산이 끝났으면 시작시간과 끝 시간을 미리 정의해둔 timers [2001][2] 배열에 넣어줍시다.

(시작시간에는 +1 해주셔야 됩니다!) 

 

 

이제 구간을 나누어 줄 건데 여기서 저는 4가지로 분류했습니다.

시작 지점은 모든 데이터 시작시간과 끝난 시점으로 잡았고

그 사이에 데이터 전송이 일어났는지를 확인하는 부분에서

 

1. A 시작 < B데이터< A시작+1초< B데이터끝 

2. B데이터< A시작< B데이터 끝 < A 시작 1초

3. A 시작 < B데이터시작/끝 < A끝

4. B데이터 시작 < A시작 < A끝 < B데이터 끝

 

말로 푸니까 복잡하네요.... 

여하튼 그림을 보고 아래로 내려오시면

첫 번째 for는 모든 데이터를 도는 for

두 번째는 시작 지점으로부터 1초를 할 건지 끝지점부터 1초를 할건지 결정하는 for

세 번째에서 이제 위에서 말한 4가지 경우를 if else if 문으로 작성해 보았습니다.

 

for(int i=0;i<lines.size();i++){
        
        for(int k=0;k<2;k++){//0은 시작위치 1은 끝난위치
            int count=1;
            for(int j=i+1;j<lines.size();j++){
    
                 if(timers[i][k]<=timers[j][0] and timers[i][k]+999>=timers[j][0] 
                    and timers[i][k]+999<timers[j][1]){

                        count+=1;
                    }
                 else if(timers[i][k]<=timers[j][1] and timers[i][k]+999>=timers[j][1] 
                         and timers[i][k]>=timers[j][0]){

                        count+=1;
                    }
                 else if(timers[i][k]<=timers[j][0] and timers[i][k]+999>=timers[j][1]){

                     count+=1;
                 }
                else if(timers[i][k]>=timers[j][0] and timers[i][k]+999<=timers[j][1])
                    count+=1;
             }  
                         answer=max(answer,count);
        }
        
    }

겹치는걸 4가지로 나눌 필요가 있을까..?라는 생각이 들긴 했지만

중복이 생길 수도 있을 것 같아서 안전하게 4개로 나누어 주었습니다.

 

그 후 max값을 출력해주시면 끝!

 

 

*all

#include <string>
#include <vector>
#include <iostream>

using namespace std;
int timers[2001][2];


int solution(vector<string> lines) {
    int answer = 0;
    if(lines.size()==1){
        return 1;
    }
    for(int i=0;i<lines.size();i++){
        int sum=0;
        sum+=stoi(lines[i].substr(11,2))*60*60*1000;
        sum+=stoi(lines[i].substr(14,2))*60*1000;
        sum+=stoi(lines[i].substr(17,2))*1000;
        sum+=stoi(lines[i].substr(20,3));
        
        int count=0;
        for(int j=0;j<5;j++){
            count+=1;
            if(lines[i][24+j]=='s'){
                count-=1;
                break;
            }
        }
        timers[i][0]=sum-stof(lines[i].substr(24,count))*1000+1;//시작시간
        timers[i][1]=sum;//끝
    }
    
    for(int i=0;i<lines.size();i++){
        
        for(int k=0;k<2;k++){
            int count=1;
            for(int j=i+1;j<lines.size();j++){
    
                 if(timers[i][k]<=timers[j][0] and timers[i][k]+999>=timers[j][0] 
                    and timers[i][k]+999<timers[j][1]){

                        count+=1;
                    }
                 else if(timers[i][k]<=timers[j][1] and timers[i][k]+999>=timers[j][1] 
                         and timers[i][k]>=timers[j][0]){

                        count+=1;
                    }
                 else if(timers[i][k]<=timers[j][0] and timers[i][k]+999>=timers[j][1]){

                     count+=1;
                 }
                else if(timers[i][k]>=timers[j][0] and timers[i][k]+999<=timers[j][1])
                    count+=1;
             }  
            answer=max(answer,count);
        }
        
    }
    
    
    
    return answer;
}

 

더 쉬운 방법 있으시면 댓 달아주세요!

 

 

틀린 점이 있다면 댓 달아주세요!