[Algorithm] KAKAO - [1차] 추석 트래픽

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

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

 

풀이방법.

 

요점1. 문자열 파싱

 

입력받은 문자열들을 파싱하여 시작시간과 종료시간을 계산한다.

 

 

요점2. 자료형 주의

밀리 초 단위로 계산이 필요하여 입력받은 시간을 밀리시간으로 변경했다.

밀리초로 변경시 숫자가 int 범위( -2147483648 ~ 2147483647)를 넘어갈 수 있으므로 

계산시 자료형을 long으로 계산했다.

 

밀리초 계산시 소수점 단위를 계산하기 위해 먼저 Double형으로 변환후 1000을 곱하여 Long 자료형으로 계산하였다.

 

 

문자열 파싱 객체

class TimeData{
    long stMillScnd;
    long endMillScnd;
    public TimeData (String logData){
        String[] logs = logData.split(" ");
        String time = logs[1];
        String term = logs[2];
        this.endMillScnd = makeStrToMille(time);
        this.stMillScnd = minusTerm(term);
    }
    public long makeStrToMille(String time){
        String[] times = time.split(":");
        long hour = Long.valueOf(times[0]) * 60 * 60 * 1000;
        long min = Long.valueOf(times[1]) * 60 * 1000;
        long second = (long)(Double.valueOf(times[2]) * 1000);
        return (hour + min + second);
    }
    public long minusTerm(String term){
        return this.endMillScnd - (long)(Double.valueOf(term.substring(0,term.indexOf("s"))) * 1000) +1;
    }
    
    public void addOffset(long offSet){
        this.stMillScnd -= offSet;
        this.endMillScnd -= offSet;
    }
    
    @Override
    public String toString() {
        return this.stMillScnd + " ~ " + this.endMillScnd;
    }
    
     @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        TimeData timeData = (TimeData) o;
        return stMillScnd == timeData.stMillScnd && endMillScnd == timeData.endMillScnd;
    }

    @Override
    public int hashCode() {
        return Objects.hash(stMillScnd, endMillScnd);
    }
}

 

 

요점3. 한 데이터가 끝나는 시점에서 비교

 

처음에 문제를 보고 해결하려 했던것은

모든 시간을 구하고 맨 처음 데이터의 시작시간부터 마지막 데이터의 끝나는 시간까지

1초씩 증가(1000 밀리초)하면서 매초 몇개의 처리가 이뤄지는지 확인하려고 했다.

하지만 이런 경우 최악의 경우

00:00:00.000 부터 23:59:59.999 시간 사이에 최대 데이터 수인 2000개가 들어오게 된다면 

 

최대 172800000 (86400 * 2000) 번 반복문을 돌아야 한다.

 

문제 예제 2를 잘 읽어보면 

'처리시간은 시작시간과 끝시간을 포함하므로'

이말은 초당 최대 처리량은 하나의 처리가 끝날 시점에서

1초동안 몇개의 처리가 더 이루어지고 있는지를 판별한다면

 

위의 반복숫자보다 훨씬 적은 량으로 데이터 처리가 가능하다.

 

전체 data 배열을 순회하면서

해당데이터의 종료시간(cur_end_time)을 받아서

다시 전체 data배열을 순회하면서 해당 끝나는 시간에서 1초내에

데이터가 존재하는 지 확인하는 방법은 아래와 같이 3가지가 존재한다.

( 순회되는 데이터의 시간 시작시간: data_start_time, 종료시간: data_end_time )

 

1 . cur_end_time <= data_start_time < cur_end_time + 1000 
2 . cur_end_time <= data_end_time < cur_end_time + 1000
3 . data_start_time <= cur_end_time, cur_end_time + 1000 <= data_end_time

 

여기서 1번 또는 2번 조건에서 자기 자신이 포함되므로 if ~ else if  조건으로 위 조건을 태워주면 처리가 가능하다.

 

public int countLines(TimeData[] datas , TimeData curTime){
        int count=0;
        long endTime = curTime.endMillScnd;
        for(TimeData data : datas){
            long t_st = data.stMillScnd;
            long t_et = data.endMillScnd;
            if(endTime <= t_st && t_st < endTime+1000){
                count++;
            }else if(endTime <= t_et && t_et < endTime + 1000){
                count++;
            }else if(t_st <= endTime && endTime+1000 <= t_et){
                count++;
            }
        }
        return count;
    }

 

이제 전체를 조회하면서 위 계산값이 최대인 값을 구해주면 답을 구할수 있게 된다.

 

public int solution(String[] lines) {
        int answer = 0;
        long offset = 0;
        long endTime = 0;
        TimeData[] datas = new TimeData[lines.length];
        for(int i=0; i<lines.length; i++){
            TimeData data = new TimeData(lines[i]);
            if(i==0) offset = data.stMillScnd;
            data.addOffset(offset);
            datas[i] = data;
        }
        int maxCount = -987654321;
        for(TimeData data : datas){
            maxCount = Math.max(maxCount, countLines(datas, data));
        }
        return maxCount;
    }

 

전체코드

 

import java.util.*;
import java.math.*;
class Solution {
    public int solution(String[] lines) {
        int answer = 0;
        long offset = 0;
        long endTime = 0;
        TimeData[] datas = new TimeData[lines.length];
        for(int i=0; i<lines.length; i++){
            TimeData data = new TimeData(lines[i]);
            if(i==0) offset = data.stMillScnd;
            data.addOffset(offset);
            datas[i] = data;
        }
        int maxCount = -987654321;
        for(TimeData data : datas){
            maxCount = Math.max(maxCount, countLines(datas, data));
        }
        
        //System.out.println(maxCount);
        return maxCount;
    }
    
    public int countLines(TimeData[] datas , TimeData curTime){
        System.out.println("cur:"+curTime);
        int count=0;
        long endTime = curTime.endMillScnd;
        for(TimeData data : datas){
            long t_st = data.stMillScnd;
            long t_et = data.endMillScnd;
            if(endTime <= t_st && t_st < endTime+1000){
                count++;
            }else if(endTime <= t_et && t_et < endTime + 1000){
                count++;
            }else if(t_st <= endTime && endTime+1000 <= t_et){
                count++;
            }
        }
        return count;
    }
}
class TimeData{
    long stMillScnd;
    long endMillScnd;
    public TimeData (String logData){
        String[] logs = logData.split(" ");
        String time = logs[1];
        String term = logs[2];
        this.endMillScnd = makeStrToMille(time);
        this.stMillScnd = minusTerm(term);
    }
    public long makeStrToMille(String time){
        String[] times = time.split(":");
        long hour = Long.valueOf(times[0]) * 60 * 60 * 1000;
        long min = Long.valueOf(times[1]) * 60 * 1000;
        long second = (long)(Double.valueOf(times[2]) * 1000);
        return (hour + min + second);
    }
    public long minusTerm(String term){
        return this.endMillScnd - (long)(Double.valueOf(term.substring(0,term.indexOf("s"))) * 1000) +1;
    }
    
    public void addOffset(long offSet){
        this.stMillScnd -= offSet;
        this.endMillScnd -= offSet;
    }
    
    @Override
    public String toString() {
        return this.stMillScnd + " ~ " + this.endMillScnd;
    }
    
     @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        TimeData timeData = (TimeData) o;
        return stMillScnd == timeData.stMillScnd && endMillScnd == timeData.endMillScnd;
    }

    @Override
    public int hashCode() {
        return Objects.hash(stMillScnd, endMillScnd);
    }
}

 

문제 풀면서 헤맸던 것들.

 

1. 초당 처리조건을 정확하게 이해하지 못함.

2. 문제를 잘못읽음. (주어진 시간이 시작시간 인줄 알아서 좀 헤맸다.)

혹시나 숫자가 커서 offset을 주어 첫 시작시간을 모두 빼주었으나.. 빼는 연산이나 그냥 연산이나 비슷한거 같음...

자기 자신 포함하는거 제거하려고 equals hashCode 추가하여 비교할라 했는데 자기 자신도 포함한 조건을 찾음..