[프로그래머스] 추석 트래픽 (Java)

프로그래머스 추석 트래픽

문제풀이

처리량이 변하는 것은 시작과 끝이다. 라는 것을 깨닫는데 굉장히 오래걸렸다. 생각했던 아이디어들은 다음과 같다.

• boolean 배열로 진짜 그래프처럼 만든다.
  • 단위가 밀리초라서 86400000개의 배열을 만들어야한다. boolean의 크기는 대략 1byte 이므로 86.4 MB의 메모리를 사용해야한다.
• 이분탐색으로 어떻게 해본다?
  • 어느 방향으로 탐색해나갈지에 대한 기준이 없다.
• 슬라이딩 윈도우
  • 항상 1초 크기의 윈도우에 처리량을 구해서 비교하면 되겠다. 근데 얼마만큼 슬라이딩 시켜야하지? 1밀리초 씩 이동하면.. 엄청난 시간이 소요된다.

잠깐, 구간을 구하는 것이 아니라 처리량이 가장 많은 1초만 구하면 된다. 근데 처리량이 변화는 시점은 하나의 데이터를 처리하는 시점과 완료한 시점이다. 그렇다면 각 로그의 시작과 끝을 윈도우의 시작으로 보고 각 윈도우에 대해서 처리량이 얼마나 되는지 확인하면 되겠다.

• 각 로그의 시작점과 끝점을 구한다.
  • 시간을 밀리초로 환산한다.
  • 시작점은 응답완료시간 - 처리시간 + 1밀리초
• 시작점과 끝점을 기준으로하는 윈도우를 만들어 처리량을 확인한다.
  • 해당 윈도우에 처리중인 로그는 다음과 같다.
    • 시작점이 윈도우에 걸쳐있는 경우
    • 끝점이 윈도우에 걸쳐있는 경우
    • 로그가 윈도우를 포함하고 있는 경우

풀고나면 어렵지 않은 문제로 느껴지는데... 아이디어를 생각해내는 것이 너무 어려웠다. 그 밖에도 문자열 처리, 밀리초 환산, 시작 시간, 끝 시간, 처리 시간 등의 시간 개념이 포함하는지 않하는지에 대한 것들이 구현을 까다롭게 했다.

구현코드

import java.util.*;

class Solution {
	public int solution(String[] lines) {
		int answer = 0;
		int[] startTimes = new int[lines.length];
		int[] endTimes = new int[lines.length];
		
		getTimes(lines, startTimes, endTimes);
		
		for(int i = 0 ; i < lines.length ; ++i) {
			int cnt = 0;
			int startOfSection = startTimes[i];
			int endOfSection = startOfSection + 1000;
			
			for(int j = 0 ; j < lines.length ; ++j) {
				if(startTimes[j] >= startOfSection && startTimes[j] < endOfSection) {
					cnt++;
				} else if(endTimes[j] >= startOfSection && endTimes[j] < endOfSection) {
					cnt++;
				} else if(startTimes[j] <= startOfSection && endTimes[j] >= endOfSection) {
					cnt++;
				}
			}

			answer = cnt > answer ? cnt : answer;
		}
		
		for(int i = 0 ; i < lines.length ; ++i) {
			int cnt = 0;
			int startOfSection = endTimes[i];
			int endOfSection = startOfSection + 1000;
			
			for(int j = 0 ; j < lines.length ; ++j) {
				if(startTimes[j] >= startOfSection && startTimes[j] < endOfSection) {
					cnt++;
				} else if(endTimes[j] >= startOfSection && endTimes[j] < endOfSection) {
					cnt++;
				} else if(startTimes[j] <= startOfSection && endTimes[j] >= endOfSection) {
					cnt++;
				}
			}

			answer = cnt > answer ? cnt : answer;
		}
		
		return answer;
	}

	private void getTimes(String[] lines, int[] startTimes, int[] endTimes) {
		for(int i = 0 ; i < lines.length ; ++i) {
			String[] log = lines[i].split(" ");
			String[] responseTime = log[1].split(":");
			int processingTime = (int)(Double.parseDouble(log[2].substring(0, log[2].length() - 1)) * 1000);
			int startTime = 0;
			int endTime = 0;
			
			endTime += Integer.parseInt(responseTime[0]) * 60 * 60 * 1000;
			endTime += Integer.parseInt(responseTime[1]) * 60 * 1000;
			endTime += (int)(Double.parseDouble(responseTime[2]) * 1000);
			startTime = endTime - processingTime + 1;
			
			startTimes[i] = startTime;
			endTimes[i] = endTime;
		}
	}
}