[프로그래머스] Lv.3: [1차] 추석 트래픽 - java

문제

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

프로그래머스

 

접근법

처음에 두 가지 방법을 생각했는데 잘 되지 않았다.

1. 문제에 있는 막대 그래프 처럼 배열을 만들어서 해결 -> 시간이 0.001초 단위로 쪼개지기 때문에 불가능

2. 이분탐색 활용 -> 탐색의 범위..? 윈도우..?가 1초로 고정이기 때문에 아무리 해도 잘 풀리지 않았다..

 

그래서 결국 아래 해설 보기를 클릭해 몇가지 힌트를 얻어왔다. 사실 자세한 해설이 있을거 같아서 들어갔던거였는데 역시 코딩은 정해진 답이 없다. 해설 조차 힌트만 줬다. 

여기서 중요한 것은 요청량이 변하는 순간은 각 로그의 시작과 끝뿐이라는 것이다. $O(nlogn)$ 으로 푸는 방법은 아직 찾지 못했는데 (앞에 더 비효율적인 풀이도 제대로 이해하지 못함... ;ㅜ) 나중에 찾아서 완벽하게 이해한다면 추가해야겠다. 

 

날짜 변환

입력받은 문자열을 어떻게 처리할지 생각해보자.

 

문제에 써있는 것처럼 로그 문자열 "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초"동안 처리된 요청을 말한다.

나 역시 이 그대로 클래스를 만들어 저장해야겠다고 생각했다. 그런데 처리 시간을 빼는 과정에서 second가 음수가 되면 minute도 수정해야하고, minute가 음수가 되면 hour를 수정해야 하고 심지어는 날짜를 수정해야하는 과정도 필요했다. 즉, 날짜간의 연산이 너무 복잡했다.

 

따라서 나는 모든 시간을 second로 나타낸 후에 계산을 했다.즉, 시간은 * 3600을 하고, 분은 * 60로 변환을 해주었다. 그런데 변환한 시간에서 T를 뺀 후 출력을 해보니 소수점이 뭔가 이상한 것을 알게되었다. 아마 부동소수점 문제인거 같았다. 그래서 소수가 아닌 정수로 계산을 하는게 좋을거 같아 * 1000을 해서 정수로 만들어주었다. 

 

구간

카카오 해설에서는 구간의 양 끝점에서만 변화가 발생한다고 해서 구간의 양 끝점에서 처리 중인 요청의 개수를 세어봤는데 다른 분들의 코드를 보니 끝나는 지점에서만 개수를 세더라... 

 

이렇게 구간을 옮기며 갯수를 세어주면 된다. 구간의 시작점을 start, 끝점을 end라고 할 때 요청의 시작 시간이 start보다 작거나 같고, 요청의 종료 시간이 end보다 크면 된다.

 

코드

import java.util.*;

class Solution {
    
    Request[] requests;
    
    public int solution(String[] lines) {
        int answer = 1;
        requests = new Request[lines.length];
        
        // 로그문자열 Request 객체로 변환
        for (int i = 0; i < lines.length; i++) {
            StringTokenizer st = new StringTokenizer(lines[i]);
            String date = st.nextToken();
            String S = st.nextToken();
            String T = st.nextToken();
            
            Request request = getRequest(S, T);
            requests[i] = request;
        }
        
        // 로그의 끝에서 처리되고 있는 요청의 개수
        for (int i = 0; i < requests.length; i++) {
            int count = 0;
            long end = requests[i].end;
            
            for (int j = 0; j < requests.length; j++) {
                if (requests[j].start < end + 1000 && requests[j].end >= end) {
                    count++;
                }
            }
            
            answer = Math.max(answer, count);
        }
        
        return answer;
    }
    
    private Request getRequest(String S, String T) {
        long t = (long) (Double.parseDouble(T.substring(0, T.length() - 1)) * 1000);
        
        // 응답완료시간 분리
        StringTokenizer st = new StringTokenizer(S, ":");
        long hour = Integer.parseInt(st.nextToken()) * 1000;
        long minute = Integer.parseInt(st.nextToken()) * 1000;
        long second = (long) (Double.parseDouble(st.nextToken()) * 1000);
        
        second += minute * 60;
        second += hour * 3600;

        return new Request(second - t + 1, second);
    }
    
    class Request {
        long start, end;
            
        public Request(long start, long end) {
            this.start = start;
            this.end = end;
        }
    }
}

 

서칭을 좀 더 한 후에 글에 살 좀 붙여야겠다.. 나도 이해 좀 하고..