[프로그래머스][JAVA] 추석 트래픽

2018 카카오 채용 코딩 테스트 문제입니다.

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

문제 확인

 

prefix sum 혹은 스위핑을 통해 풀 수 있습니다.

 

풀이

 

처리 시작시간을 1, 처리가 끝난 시간을 -1로 두고 각 점들을 배열에 기록합니다. 이들을 시간 순으로 정렬하여 prefix sum을 통해 현재 지점에서 처리하는 중인 트래픽을 구하고 현재 지점부터 1초 구간 안에 있는 트래픽을 구합니다.

 

주의해야 할 점은 처리가 끝난 시간에서도 트래픽으로 간주하므로 해당 지점을 계산 시에는 -1 대신 0으로 두어야 합니다.

 

코드

import java.util.*;
class node implements Comparable<node>{
    double key;//시각
    int val;//트래픽 시작지점 : 1, 끝지점 -1
    node(double key, int val){
        this.key = key;
        this.val = val;
    }
 
    @Override
    public int compareTo(node t) {//정렬 함수
        if(this.key < t.key)
            return -1;
        else if(this.key != t.key)
            return 1;
        return 0;
    }
}
class Solution {
    public int solution(String[] lines) {
       node[] ary = new node[lines.length << 1];
        int idx = 0;
        for(String t : lines) {
            String[] log = t.split(" ");
            String[] time_log = log[1].split(":");
            double end = Double.parseDouble(time_log[0])*3600 + //작업 끝시간 : line
                    Double.parseDouble(time_log[1])*60 + 
                    Double.parseDouble(time_log[2]);
            double start = end - Double.parseDouble(log[2].replace("s", "")) + 0.001;//작업 시작 시간 
            end = (double)((int)(end * 1000))/1000;
            start = (double)((int)(start * 1000))/1000;//소수점 3자리 까지
            ary[idx++] = new node(start, 1); 
            ary[idx++] = new node(end, -1);
        }
        Arrays.sort(ary);//정렬
        int sum = 0, mx = -1;//sum : 현재 지점에서의 트래픽 : prefix sum
        
        for(int i=0;i<idx;i++) {
            int val = sum + (ary[i].val== 1 ? 1 : 0); //현재 끝 지점인 경우도 포함하기 위해 0
            
            for(int j=i+1;j<idx;j++) {    
                if(ary[j].key>=ary[i].key + 1) break;//1초 이상의 지점이 나오면 break;
                if(ary[j].val==1)//새로운 트래픽 : 1
                    val++;
            }
            mx = val > mx ? val : mx;
            sum += ary[i].val;//prefix sum
        }
        
        return mx;
    }
}

정확성 테스트

테스트 1 〉	통과 (1.41ms, 53.3MB)
테스트 2 〉	통과 (23.19ms, 55.1MB)
테스트 3 〉	통과 (39.29ms, 54.8MB)
테스트 4 〉	통과 (1.06ms, 52MB)
테스트 5 〉	통과 (3.90ms, 54.2MB)
테스트 6 〉	통과 (4.48ms, 53.6MB)
테스트 7 〉	통과 (22.61ms, 55.5MB)
테스트 8 〉	통과 (19.48ms, 54.9MB)
테스트 9 〉	통과 (3.52ms, 53.2MB)
테스트 10 〉	통과 (1.36ms, 51.8MB)
테스트 11 〉	통과 (1.22ms, 52.8MB)
테스트 12 〉	통과 (21.89ms, 55.3MB)
테스트 13 〉	통과 (4.25ms, 52.3MB)
테스트 14 〉	통과 (1.01ms, 52.4MB)
테스트 15 〉	통과 (1.01ms, 54.1MB)
테스트 16 〉	통과 (0.99ms, 52.6MB)
테스트 17 〉	통과 (1.05ms, 53.7MB)
테스트 18 〉	통과 (94.80ms, 57.7MB)
테스트 19 〉	통과 (40.20ms, 56.5MB)
테스트 20 〉	통과 (45.46ms, 57.1MB)
테스트 21 〉	통과 (1.03ms, 52.1MB)
테스트 22 〉	통과 (0.92ms, 52.6MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0