추석 트래픽

Posted on Edited on In , ,

문제정의

1초 동안의 최대 트래픽이 몇개가 되는지 구하는 문제이다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class test {

    public static final int START = 0;
    public static final int END = 1;

    public class Time{
        int ms;
        int state;
    
        public Time(int t, int s){
            this.ms = t;
            this.state = s;
        }
    }
    
    public static void main(String[] args) {
        String[] lines = {"2016-09-15 01:00:04.002 2.0s", "2016-09-15 01:00:07.000 2s"};
        List<Time> times = new ArrayList<Time>();
        for(String line : lines)
        {
            String[] line_info = line.split(" ");
            //종료시간을 0.001초 단위로 환산하자
            String[] time_str = line_info[1].split(":");
            int end_t = Integer.parseInt(time_str[0])*3600000 + Integer.parseInt(time_str[1])*60000 + Integer.parseInt(time_str[2].split("\\.")[0])*1000 + Integer.parseInt(time_str[2].split("\\.")[1]);
            //지속시간을 구해볼까
            String last_time_str = line_info[2].substring(0, line_info[2].length()-1);
            String[] last_time_arr = last_time_str.split("\\.");
            int last_t = Integer.parseInt(last_time_arr[0])*1000;
            if(last_time_arr.length > 1)
                last_t += Integer.parseInt(last_time_arr[1]);
            
            //이제 시작 시간을 구하자(끝시간 - 지속시간 +1)
            int start_t = end_t - last_t + 1;

            test obj = new test();
            test.Time t = obj.new Time(start_t, START);
            times.add(t);
            t = obj.new Time(end_t+999, END);
            times.add(t);
        
        }

        Comparator<Time> t_comparator = new Comparator<Time>(){
            @Override
            public int compare(Time o1, Time o2)
            {
                if(o1.ms != o2.ms)
                    return Integer.compare(o1.ms, o2.ms);
                return Integer.compare(o1.state, o2.state);
            }
        };

        Collections.sort(times, t_comparator);

        int working = 0, max_cnt = 0;
        for(int i = 0; i < times.size(); i++)
        {
            if(times.get(i).state == START)
                ++working;
            else
                --working;

            max_cnt = Math.max(working, max_cnt);
        }

        System.out.println(max_cnt);
    }

}

이 문제에서의 핵심 아이디어는 어떻게 1초 트래픽을 어디서 볼 것인가 이다. 밀리초마다 단위를 옯겨가면서 하면 연산량이 많아진다. 따라서 우리는 언제 트래픽의 개수가 변하는지 생각해봐야 한다. 생각해보면 구간의 양 끝에서 트래픽이 변할 수 있다는 것을 알 수 있다. 이 아이디어를 가지고 코드를 살펴보자.

8~16번째 라인을 보면 Time에 대한 정의를 해놓은 것을 볼 수 있다. ms는 시간을 의미하고 state는 구간의 처음에 해당하는지 끝에 해당하는지 알려주는 변수이다. state에는 START또는 END가 들어가며, 이는 각각 0과 1이다.

24~46번째는 로그에 있는 시간을 ms단위로 바꾼 뒤, 이를 리스트에 저장하는 과정이다. 첫구간과 끝구간을 저장하는데 잘 보면 end_T+999를 저장한 것을 볼 수 있다. 이는 뒤 구간을 포함해서 1초안에 해당하면 동시에 진행되는 작업물로 보기 때문이다(ex 4.001초에 완료한것과 5초에 시작하는 트래픽은 동시에 일어난 것으로 본다).

48~57번째 줄에서는 정렬을 한다. 정렬을 할 땐 기본적으로 시작 시각을 기준으로 하고 시각 기준이 같을 시 시작 구간인 부분을 우선으로 한다. 왜냐하면 동시에 시작하고 끝난 트래픽도 두 작업을 같이 했다고 보기 때문이다.

정렬이 끝나고 난 뒤 배열을 돌면서 구간이 START 이면 working에 1을 더해주고 그렇지 않으면 1을 뺀다. 구간에만 집중하여 문제를 풀면 \(O(nlogn)\)만에 문제를 풀 수 있다.

테스트



아이디어는 다 생각이 났었는데 코드로 이 아이디어를 어떻게 풀어나가야 할지 몰라 난감했다. 거의 끝까지 왔는데 미처 못 풀어서 다른 사람의 풀이를 참고해서 짰는데 속상하다. 카카오 블라인드 테스트 중에서 가장 어려운 문제라고 하던데 그래도 아이디어는 생각해 낸 것까지 올라온 걸로 위안을 삼기로 했다. 포기하지 말자.