프로그래머스 - [1차] 추석 트래픽

[1차] 추석 트래픽 : https://programmers.co.kr/learn/courses/30/lessons/17676

Problems

---

Solves

처음에는 첫번째 로그의 처리 시작시간부터 마지막 로그의 처리 끝시간 까지 비교하면서 처리하려고 했더니 로직도 복잡하고 막막했었다.
해설을 보고나서야 방법이 떠올랐다.

일단 각 로그의 시작시간과 끝시간을 밀리초로 환산한다. 그리고 시작시간 = 끝시간 - 처리시간 + 1(밀리초)
처리량이 최소 하나 이상이 있는 시간은 각 로그의 시작시간과 끝시간을 기준으로 1초(1000ms)이다.
각 로그의 시작시간 ~ 시작시간+1초, 끝시간 ~ 끝시간+1초의 시간안에 처리되고 있는 갯수를 카운트해서 가장 큰 값을 구하면되는것이다.
즉, 각 로그의 시작시간과 끝시간을 윈도우의 시작으로 보고 각 윈도우에 포함되는 처리량이 얼마나 되는지 확인하면 된다. (여기서 윈도우는 시작시간과 끝시간을 기준으로 1초 뒤의 시간 까지의 범위)

• 윈도우에 포함되어 처리량을 구하는 기준
  • 로그의 시작 시간이 윈도우에 포함되는 경우
  • 로그의 끝 시간이 윈도우에 포함되는 경우
  • 로그의 수행시간이 윈도우를 포함하는 경우

---

Code

class Solution {
    public int solution(String[] lines) {
    	//각 로그의 시작시간 저장
        int[] startTimes = new int[lines.length];
        //각 로그의 끝시간 저장
        int[] endTimes = new int[lines.length];
		//각 로그의 시간 설정 및 초기화
        setTime(lines, startTimes, endTimes);
        
        //최대 처리량
        int processCount=0;
        //시작시간을 기준으로 윈도우 생성 및 비교
        for(int i=0;i<startTimes.length;i++){
       		//현재 윈도우의 처리량
            int count = 0;
            int startOfWindow = startTimes[i];
            //시작시간에서 +1초는 시간시간+1초에서 1밀리초가 빠져있음(현재 모든 시간은 밀리초로 환산된 상태)
            int endOfWindow = startTimes[i]+999;
            
            for(int j=0;j<lines.length;j++){
            	/*주석되어 있는 코드는 처음에 로그들은 시간이 정렬되어서 주어진다는 것만 보고
                 윈도우의 마지막 시간보다 처리 시작시간이 뒤에 발생했다면 
                 그 뒤는 로그는 볼 필요가 없다고 생각하고 반복문을 멈추었었다.
                 3,18번 테스트케이스에서 계속 실패가 떠서 반례를 찾다가 끝시간을 기준으로 로그가 정렬 되어있었다.
                 끝시간으로 정렬되어있다면 처리 시간으로 인해 시작시간은 정렬이 되지 않기때문에 발생한것이다.
                 그래서 해당 코드를 제거하니 통과.
                */
                //if(startTimes[j] > endOfWindow) break;
                
                //시작시간이 윈도우에 포함되는 경우
                if(startTimes[j]>=startOfWindow && startTimes[j]<=endOfWindow){
                    count++;
                }
                //끝시간이 윈도우에 포함되는 경우
                else if(endTimes[j]>=startOfWindow && endTimes[j]<=endOfWindow){
                    count++;
                }
                //로그의 수행시간이 윈도우를 포함하는 경우
                else if(startTimes[j]<=startOfWindow && endTimes[j]>=endOfWindow){
                    count++;
                }
            }
            //처리량의 최대값을 갱신
            processCount = Math.max(processCount, count);
        }
        
        //로그의 끝시간을 기준으로 윈도우 생성 및 비교(위의 처리 과정은 동일)
        for(int i=0;i<endTimes.length;i++){
            int count=0;
            int startOfWindow = endTimes[i];
            int endOfWindow = endTimes[i]+999;
            
            for(int j=0;j<lines.length;j++){
                // if(startTimes[j]>endOfWindow) break;
                
                if(startTimes[j]>=startOfWindow && startTimes[j]<=endOfWindow){
                    count++;
                }else if(endTimes[j]>=startOfWindow && endTimes[j]<=endOfWindow){
                    count++;
                }else if(startTimes[j]<startOfWindow && endTimes[j]>endOfWindow){
                    count++;
                }
            }
            processCount = Math.max(processCount, count);
        }
        
        return processCount;
    }
    
    //각 로그들의 시간을 밀리초로 반환 및 시작시간 리스트, 끝시간 리스트 초기화해주는 함수
    void setTime(String[] lines, int[] startLines, int[] endLines){
        for(int i = 0;i<lines.length;i++){
            String[] log = lines[i].split(" ");
            
            String[] endTimeArr = log[1].split(":");
            int endTime = 0;
            endTime += Integer.parseInt(endTimeArr[0])*60*60*1000;
            endTime += Integer.parseInt(endTimeArr[1])*60*1000;
            endTime += (int)(Double.parseDouble(endTimeArr[2])*1000);
            
            int processingTime = (int)(Double.parseDouble(log[2].substring(0,log[2].length()-1))*1000);
            int startTime = endTime - processingTime + 1;
            
            startLines[i] = startTime;
            endLines[i] = endTime;
        }
    }
}

---

Result

시간과 관련된 문제는 처음이였다. 시간은 어떻게 처리해야하나 고민을 많이했었는데 밀리초로 반환해서 처리하니 시간의 이전, 이후 관리가 수월했다. 앞으로 참고해야겠다.
혼자 풀때는 죽어도 모르겠었는데 해설보고 풀고나니 그렇게 어렵게 생각할정도였나 싶었지만 아이디어를 생각해내는것 자체가 난이도 있는 문제인것같다.