2018 - [1차] 추석 트래픽

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

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

[ 문제풀이 ]

시간을 초로 환산하여 계산하는 방법을 알고 있으면 조금 수월하게 해결할 수 있는 문제이다. 이전에 비슷한 유형을 풀어봤기 때문에 주어진 문자열을 파싱해서 초로 환산하여 해결하였다.

​"2016-09-15 01:00:04.002 2.0S" 형태의 문자열을 파싱해서 시작 시간과 끝 시간을 구해줘야 한다. 9월 15일의 데이터를 처리하는 것이기 때문에 연도는 넘어가고 시간만 계산해주면 된다.

​초가 소수점 셋째 자리까지 있기 때문에 초에 1000을 곱해줘서 정수로 만들어준다. 분과 시는 각각 60000(60 x 1000), 3600000(60 x 60 x 1000)을 곱해주면 초로 환산할 수 있다.

​시간을 초로 환산한 다음은 주어진 조건대로 1초 사이의 처리량을 구해주면 된다.

​

처음에는 투포인터를 활용해서 O(N)의 시간 복잡도로 해결하려고 했는데 3번과 18번 테스트케이스에서 자꾸 틀렸다.

int right = list.get(0).end;
int idx = 0, count = 1;
for (int i = 1; i < list.size(); ) {
    int start = list.get(i).start;
            
    //현재 기준 right + 1초보다 작은 경우
    if (start - 1000 < right) {
        count++;
        i++;
    } 
    //현재 기준 right + 1초보다 크거나 같은 경우
    else {
        count--;
        right = list.get(++idx).end;
    }
            
    answer = Math.max(answer, count);
}

계속 시도해봤지만 어떤 케이스를 놓치고 있는 것인지 해결하기가 어려워서 결국 모든 경우를 탐색하는 O(N^2)의 시간 복잡도로 해결하였다.

import java.util.*;

class Solution {
    class Node {
        int start, end;
        
        public Node(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
    
    public int solution(String[] lines) {
        int answer = 1;
        
        ArrayList<Node> list = new ArrayList<>();
        for (String s : lines) {
            StringTokenizer st = new StringTokenizer(s);
            st.nextToken();
            
            //주어진 문자열을 초로 환산
            String[] time = st.nextToken().split(":");
            int end = Integer.parseInt(time[0]) * 3600000 + Integer.parseInt(time[1]) * 60000 + (int)(Double.parseDouble(time[2]) * 1000);
            
            String diff = st.nextToken();
            int start = end - (int)(Double.parseDouble(diff.substring(0, diff.length() - 1)) * 1000) + 1;
            
            list.add(new Node(start, end));
        }
            
        int cnt = 0;
        for (int i = 0; i < list.size(); ++i){
            int start = list.get(i).start;
            cnt = 1;
            
            //시작 시간 + 1초보다 작은 경우
            for (int j = i + 1; j < list.size(); ++j){
                if (list.get(j).start <= start + 999){
                    cnt++;
                }
            }
            
            answer = Math.max(answer, cnt);
            
            cnt = 1;
            int end = list.get(i).end;
            
            //끝 시간 + 1초보다 작은 경우
            for (int j = i + 1; j < list.size(); ++j){
                if (list.get(j).start <= end + 999){
                    cnt++;
                }
            }
            
            answer = Math.max(answer, cnt);
        }
        
        return answer;
    }
}