[Programmers] 추석 트래픽

문제

 

2018 KAKAO BLIND RECRUITMENT > [1차] 추석 트래픽

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

 

 

아이디어

 

이번 문제의 아이디어는 1초간 처리되는 요청의 위치를 지정하는 방법이라고 생각합니다.

 

제가 생각한 위치 지정하는 방법은 다음과 같습니다.

 

• 로그가 시작하는 시점부터 1초간
• 로그가 종료되는 시점부터 1초간

 

모든 시간에 대한 경우를 탐색할 수도 있지만 해당 방법은 시간 초과가 날 수 있는 요소이기 때문에 주어진 로그를 기준으로 삼아 위치를 지정한다면 문제를 푸는데 문제가 없게 됩니다.

 

위의 방법으로 최대 처리량을 구하는 시간대를 구하게 된다면 단순히 해당 시간대에 포함되는 로그가 몇 개가 있는지를 카운트해주면 됩니다.

 

그중 구할 수 있는 최댓값이 결국 답으로 이어지게 됩니다.

 

 

구현 코드 (Java)

 

import java.util.*;

class Solution {
    public int solution(String[] lines) {
        List<Node> list = new ArrayList<Node>();
        
        for(int i=0; i<lines.length; i++) {
        	String line_split[] = lines[i].split(" ");
        	String endTime_split[] = line_split[1].split(":");
        	int spendTime = (int) (Double.valueOf(line_split[2].replace("s", ""))*1000);
        	int end = Integer.valueOf(endTime_split[0])*60*60*1000 + 
        			  Integer.valueOf(endTime_split[1])*60*1000 + 
        			  Integer.valueOf(endTime_split[2].replace(".", ""));
        	int start = end - spendTime + 1;
        	
        	Node node = new Node(start, end); // 밀리초로 시간 변경하여 저장
        	
        	list.add(node);
        }
        
        int res = Integer.MIN_VALUE;
        
        for(int i=0; i<list.size(); i++) {
        	Node node = list.get(i);
        	
        	// start를 기준으로 뒤의 1초를 바라볼 때
        	int count = 0;
        	for(int j=0; j<list.size(); j++) {
        		Node targetNode = list.get(j);
        		
        		if(node.start > targetNode.end || node.start+999 < targetNode.start) { // 범위에 벗어나는 경우는 continue
        			continue;
        		}
        		
        		count++;
        	}
        	
        	res = Math.max(res, count);
        	
        	// end를 기준으로 뒤의 1초를 바라볼 때
        	count = 0;
        	for(int j=0; j<list.size(); j++) {
        		Node targetNode = list.get(j);
        		
        		if(node.end > targetNode.end || node.end+999 < targetNode.start) { // 범위에 벗어나는 경우는 continue
        			continue;
        		}
        		
        		count++;
        	}
        	
        	res = Math.max(res, count);
        }
        
        
        return res;
    }
    
    private static class Node { // 트래픽 정보
    	int start, end;

		public Node(int start, int end) {
			this.start = start;
			this.end = end;
		}
    }
}

 

 

 

읽어주셔서 감사합니다.